%% \begin{aosachapter}{The NoSQL Ecosystem}{s:nosql}{Adam Marcus}
\begin{aosachapter}{NoSQLを取り巻く世界}{s:nosql}{Adam Marcus}
%% Based on EN-Revision r229

%% Unlike most of the other projects in this book, NoSQL is not a tool, but
%% an ecosystem composed of several complimentary and competing tools.
%% The tools branded with the NoSQL monicker provide an alternative to
%% SQL-based relational database systems for storing data. To understand
%% NoSQL, we have to understand the space of available tools, and see how
%% the design of each one explores the space of data storage possibilities.
他の大半の章とは異なり、NoSQLは単体のツールを表す言葉ではない。時には補完しあったり時には競合したりするさまざまなツール群からなる生態系を指す用語である。NoSQLと名付けられたツール群は、SQLベースのリレーショナルデータベースとは異なる方式でデータを格納する仕組みを提供する。NoSQLを理解するには、まずどんなツールが存在するのかを理解し、そしてそれぞれのツールがどのようにデータを格納するのかという設計を知る必要がある。

%% If you are considering using a NoSQL storage system, you should first
%% understand the wide space of options that NoSQL systems span.  NoSQL
%% systems do away with many of the traditional comforts of relational
%% database systems, and operations which were typically encapsulated
%% behind the system boundary of a database are now left to application
%% designers.  This requires you to take on the hat of a systems
%% architect, which requires a more in-depth understanding of how such
%% systems are built.
NoSQLをストレージシステムとして使おうと検討するときにまず理解すべきことは、NoSQLの中にもさまざまなシステムが存在するということである。NoSQLシステムは、伝統的なリレーショナルデータベースシステムが持つ快適な機能の多くを廃止した。そして、これまでデータベース側に隠蔽されていた操作をアプリケーションの設計側に押し出したのだ。つまり、システムアーキテクトの立場で考えると、これらのシステムの仕組みをより深く知っておく必要があるということだ。

%% \begin{aosasect1}{What's in a Name?}
\begin{aosasect1}{その名の由来は?}

%% In defining the space of NoSQL, let's first take a stab at defining
%% the name.  Taken literally, a NoSQL system presents a query interface
%% to the user that is not SQL\@.  The NoSQL community generally takes a
%% more inclusive view, suggesting that NoSQL systems provide
%% alternatives to traditional relational databases, and allow developers
%% to design projects which use \emph{Not Only} a SQL interface. In some
%% cases, you might replace a relational database with a NoSQL
%% alternative, and in others you will employ a mix-and-match approach to
%% different problems you encounter in application development.
NoSQLの世界を語る前に、まずはその名前をきちんと定義してみよう。NoSQLシステムとは、文字通りにとらえるとSQLではない問い合わせインターフェイスを持つシステムのことである。ただ、NoSQLコミュニティではもう少し包括的にとらえている。NoSQLシステムとは今までのリレーショナルデータベースの代替となるものであり、開発者がシステムを設計するときに、SQLにとらわれずに(\emph{Not Only} SQL)いろいろなインターフェイスを使えるようにするものだという考え方である。リレーショナルデータベースをその代替となるNoSQLで完全に置き換えることがあるかもしれないし、両者を組み合わせてアプリケーション開発時のさまざまな問題に対応していくこともあるかもしれない。

%% Before diving into the world of NoSQL, let's explore the cases where
%% SQL and the relational model suit your needs, and others where a NoSQL
%% system might be a better fit.
NoSQLの世界に飛び込む前に少し考えてみよう。SQLや関係モデルが適するのはどのような場面だろうか。そしてNoSQLシステムのほうがより適しているのはどんな場合だろうか。

%% \begin{aosasect2}{SQL and the Relational Model}
\begin{aosasect2}{SQLと関係モデル}

%% SQL is a declarative language for querying data.  A declarative
%% language is one in which a programmer specifies \emph{what} they want
%% the system to do, rather than procedurally defining \emph{how} the
%% system should do it.  A few examples include: find the record for
%% employee 39, project out only the employee name and phone number from
%% their entire record, filter employee records to those that work in
%% accounting, count the employees in each department, or join the data
%% from the employees table with the managers table.
SQLは、データを問い合わせるための宣言型の言語である。宣言型の言語とは、そのシステムに\emph{何を}させたいのかをプログラマーが指定する言語のことである。そのシステムが\emph{どのように}動くべきなのかを手続き的に定義するのではない。いくつか例を示そう。39番の社員を探したり、レコード全体から社員名と電話番号だけを取り出したり、経理部門に属する社員のレコードだけに絞り込んだり、部署ごとの社員数を調べたり、社員テーブルのデータを管理職テーブルと連結させたりといった操作だ。

%% To a first approximation, SQL allows you to ask these questions without
%% thinking about how the data is laid out on disk, which indices to use
%% to access the data, or what algorithms to use to process the data.  A
%% significant architectural component of most relational databases is a
%% \emph{query optimizer}, which decides which of the many logically
%% equivalent query plans to execute to most quickly answer a query.
%% These optimizers are often better than the average database user, but
%% sometimes they do not have enough information or have too simple a
%% model of the system in order to generate the most efficient execution.
おおざっぱに言うと、SQLを使えば、データのディスク上での配置や使うインデックスそしてデータを処理するアルゴリズムを知らなくてもこれらの問いに答えられるということである。多くのリレーショナルデータベースのアーキテクチャ上で重要となるパーツが\emph{クエリオプティマイザ}だ。これは、論理的に等価であるいろいろな問い合わせプランの中から最も効率的な問い合わせができるものを見つける。このオプティマイザは、たいていの場合はふつうのデータベースユーザーよりも賢い。しかし時には、必要な情報が不足していたりデータモデルがあまりにもシンプルすぎたりといった理由で最適な実行計画を生成できないこともある。

%% Relational databases, which are the most common databases used in
%% practice, follow the \emph{relational data model}.  In this model, different
%% real-world entities are stored in different tables.  For example, all
%% employees might be stored in an Employees table, and all departments
%% might be stored in a Departments table.  Each row of a table has
%% various properties stored in columns.  For example, employees might
%% have an employee id, salary, birth date, and first/last names.  Each of these properties
%% will be stored in a column of the Employees table.
現在もっとも一般的に使われているデータベースがリレーショナルデータベースで、これは\emph{関係データモデル}に従っている。このモデルは、現実世界のさまざまなエンティティをそれぞれ別のテーブルに格納する。たとえば、社員の情報はEmployeesテーブルに格納し、部署の情報はDepartmentsテーブルに格納するといったものだ。テーブルの各行は、さまざな項目を保持している。たとえば社員の持つ情報としては社員IDや給与、生年月日、そして姓名などである。これらの項目が、Employeesテーブルの各カラムに格納される。

%% The relational model goes hand-in-hand with SQL\@.  Simple SQL queries,
%% such as filters, retrieve all records whose field matches some test
%% (e.g., employeeid = 3, or salary > \$20000).  More complex constructs
%% cause the database to do some extra work, such as joining data from
%% multiple tables (e.g., what is the name of the department in which
%% employee 3 works?).  Other complex constructs such as aggregates
%% (e.g., what is the average salary of my employees?) can lead to
%% full-table scans.
関係モデルはSQLと密接に関連している。フィルタのような単純なSQL問い合わせは、あるフィールドが何らかの条件(例: employeeid = 3、salary > \$20000)にマッチするレコードをすべて取得する。層少し複雑な構造を使って、データベースに他の作業をさせることもできる。複数のテーブルからのデータの結合(例: 社員番号3番の社員が所属する部署の部署名は?)などである。それ以外にも、集約(例: 従業員の給与の平均額は?)などの操作もでき、この場合はテーブル全体のスキャンが発生する。

%% The relational data model defines highly structured entities with
%% strict relationships between them.  Querying this model with SQL
%% allows complex data traversals without too much custom development.
%% The complexity of such modeling and querying has its limits, though:
関係モデルでは高度に構造化されたエンティティを定義し、さらにそれらの間に厳格なリレーションシップも定義する。このようなモデルに対してSQLで問い合わせをすれば、カスタム開発なしで複雑なデータの取得もできるようになる。しかし、このように複雑なモデルや問い合わせにも制限はある。

\begin{aosaitemize}

  %% \item Complexity leads to unpredictability.  SQL's expressiveness
  %% makes it challenging to reason about the cost of each query, and thus the
  %% cost of a workload.  While simpler query languages might complicate
  %% application logic, they make it easier to provision data storage
  %% systems, which only respond to simple requests.
  \item 複雑さは予測不可能性につながる。SQLは表現力がありすぎるので、個々のクエリのコスト、つまりその作業量に関するコストをきちんと考えないといけなくなる。問い合わせ言語をシンプルにするとアプリケーションのロジックが複雑になってしまうが、データストレージシステムを用意するのは簡単になる。単にシンプルなリクエストに応答できればそれで済むのだから。

  %% \item There are many ways to model a problem.  The relational data
  %% model is strict: the schema assigned to each table specifies the
  %% data in each row.  If we are storing less structured data, or rows
  %% with more variance in the columns they store, the relational model
  %% may be needlessly restrictive.  Similarly, application developers
  %% might not find the relational model perfect for modeling every kind
  %% of data.  For example, a lot of application logic is written in
  %% object-oriented languages and includes high-level concepts such as
  %% lists, queues, and sets, and some programmers would like their
  %% persistence layer to model this.
  \item 問題をモデル化する方法は一つではない。関係データモデルは厳格なモデルであり、各テーブルに設定されたスキーマが個々の行のデータを規定する。あまり構造化されていないデータを格納する場合や行によって格納するカラムにばらつきがある場合などは、関係モデルだと制約が大きすぎることになる。アプリケーションの開発者の視点で考えても、関係モデルがあらゆる種類のデータを完璧にモデリングできるとは言えない。たとえば、アプリケーションのロジックの多くはオブジェクト指向の言語で書かれており、より高レベルの概念であるリストやキュー、セットなどを使っている。プログラマーの中には、永続層でこれらをモデリングしたいという人もいるだろう。

  %% \item If the data grows past the capacity of one server, then the
  %% tables in the database will have to be partitioned across computers.
  %% To avoid JOINs having to cross the network in order to get data in
  %% different tables, we will have to denormalize it.  Denormalization
  %% stores all of the data from different tables that one might want to
  %% look up at once in a single place.  This makes our database look
  %% like a key-lookup storage system, leaving us wondering what other
  %% data models might better suit the data.
  \item データの量が増加して一つのサーバーでは保持しきれなくなると、データベース内のテーブルをパーティションに区切って複数のコンピューターで管理する必要がある。別のテーブルにあるデータを取得するためにネットワークをまたがるJOINをするなどということは回避するには、テーブルを非正規化しなければならない。非正規化とは、さまざまなテーブルにあるデータの中で一度に使いたいものをすべて一か所にまとめて格納するということである。これにより、データベースはまるでキーで検索する方式のストレージシステムのようになるが、他にもっと適したデータモデルがないのかという思いは残る。

\end{aosaitemize}

%% It's generally not wise to discard many years of design considerations
%% arbitrarily.  When you consider storing your data in a database,
%% consider SQL and the relational model, which are backed by decades of
%% research and development, offer rich modeling capabilities, and
%% provide easy-to-understand guarantees about complex operations.  NoSQL
%% is a good option when you have a specific problem, such as large
%% amounts of data, a massive workload, or a difficult data modeling
%% decision for which SQL and relational databases might not have been
%% optimized.
長年にわたって検討されてきた設計を独断で切り捨ててしまうのは、あまりよい考えではない。データをデータベースに格納するときにはSQLと関係モデルを検討しよう。これは何十年にもわたる研究と開発のたまものであり、高度なモデリングができる。また、複雑な操作も容易に理解できることは請け合う。NoSQLが選択肢にあがるのは、何か特有の問題がある場合だ。たとえば大量のデータを扱う必要があったり作業量が膨大になったり、SQLとリレーショナルデータベースではうまく最適化できないようなデータモデリングを採用した場合などである。

\end{aosasect2}

%% \begin{aosasect2}{NoSQL Inspirations}
\begin{aosasect2}{NoSQLのはじまり}

%% The NoSQL movement finds much of its inspiration in papers from the
%% research community.  While many papers are at the core of design
%% decisions in NoSQL systems, two stand out in particular.
NoSQLムーブメントの起源をたどれば、その大半は研究コミュニティの論文に行き着く。NoSQLシステムの設計に関する決断には多くの論文が絡んでいるが、中でも特筆すべきなのが次の二つである。

%% Google's BigTable~\cite{bib:bigtable} presents an interesting data model,
%% which facilitates sorted storage of multi-column historical data.
%% Data is distributed to multiple servers using a hierarchical
%% range-based partitioning scheme, and data is updated with strict
%% consistency (a concept that we will eventually define in
%% \aosasecref{sec.nosql.consistency}).
GoogleのBigTable~\cite{bib:bigtable}は興味深いデータモデルを提示した。このモデルでは、複数列からなる履歴データを分類して格納する。データを複数のサーバーに分散させるために階層型のレンジベースパーティショニング方式を用い、データは厳密な整合性(この概念については\aosasecref{sec.nosql.consistency}で定義する)のもとで更新される。

%% Amazon's Dynamo~\cite{bib:amazon:dynamo} uses a different key-oriented distributed datastore.
%% Dynamo's data model is simpler, mapping keys to application-specific
%% blobs of data.  The partitioning model is more resilient to failure,
%% but accomplishes that goal through a looser data consistency approach
%% called eventual consistency.
AmazonのDynamo~\cite{bib:amazon:dynamo}は、キー指向の分散型データストアを用いる。Dynamoのデータモデルはシンプルで、アプリケーション固有のデータのblobにキーをマッピングする。パーティショニング方式は障害からの回復機能を持つが、それを実現するためにデータの整合性はより緩やかな手法(結果整合性)で管理している。

%% We will dig into each of these concepts in more detail, but it is
%% important to understand that many of them can be mixed and matched.
%% Some NoSQL systems such as HBase\footnote{\url{http://hbase.apache.org/}} sticks closely to the BigTable
%% design. Another NoSQL system named Voldemort\footnote{\url{http://project-voldemort.com/}} replicates many of
%% Dynamo's features.  Still other NoSQL projects such as Cassandra\footnote{\url{http://cassandra.apache.org/}} have
%% taken some features from BigTable (its data model) and others from
%% Dynamo (its partitioning and consistency schemes).
これら二つの概念についてこれから詳細を説明するが、その概念の多くは互いに組み合わせて使えるものだと理解しておくことが大切だ。たとえば、NoSQLシステムのひとつであるHBase\footnote{\url{http://hbase.apache.org/}}は、BigTableの設計に忠実な作りになっている。別のNoSQLシステムであるVoldemort\footnote{\url{http://project-voldemort.com/}}は、Dynamoの機能の多くを再現している。さらに別のNoSQLシステムであるCassandra\footnote{\url{http://cassandra.apache.org/}}の場合は、BigTableから引き継いだ機能(データモデル)もあればDynamoから引き継いだ機能(パーティショニングや整合性管理の方式)もある。

\end{aosasect2}

%% \begin{aosasect2}{Characteristics and Considerations}
\begin{aosasect2}{特徴と検討事項}

%% NoSQL systems part ways with the hefty SQL standard and offer simpler
%% but piecemeal solutions for architecting storage solutions.  These
%% systems were built with the belief that in simplifying how a database
%% operates over data, an architect can better predict the performance of
%% a query.  In many NoSQL systems, complex query logic is left to the
%% application, resulting in a data store with more predictable query
%% performance because of the lack of variability in queries
NoSQLシステムは、大掛かりなSQL標準規格と決別して、ストレージの設計に関してシンプルながらも段階的なソリューションを提供する。その思想は、「データベースがデータを操作する方法を単純化すればするほど、アーキテクトは問い合わせのパフォーマンスを予測しやすくなる」というものだ。NoSQLシステムの多くは、複雑な問い合わせロジックをアプリケーション側に任せている。その結果、データストア側では問い合わせのパフォーマンスを予測しやすくなる。問い合わせの種類が限られてくるからである。

%% NoSQL systems part with more than just declarative queries over the
%% relational data.  Transactional semantics, consistency, and durability
%% are guarantees that organizations such as banks demand of databases.
%% \emph{Transactions} provide an all-or-nothing guarantee when combining
%% several potentially complex operations into one, such as deducting
%% money from one account and adding the money to another.  \emph{Consistency}
%% ensures that when a value is updated, subsequent queries will see the
%% updated value.  \emph{Durability} guarantees that once a value is updated, it
%% will be written to stable storage (such as a hard drive) and
%% recoverable if the database crashes.
NoSQLシステムは、リレーショナルデータに単に宣言型の問い合わせ機能を追加するものとは一線を画する。トランザクション特性や整合性、永続性といった機能は、銀行などの組織のデータベースに求められる要件を満たすことを保証するものだ。\emph{トランザクション}は、複数の込み入った操作をひとまとめにして「すべて成功」か「すべて失敗」かのいずれかになることを保証する。たとえば、ある口座から引き落とした資金を別の口座に入金するなどといった操作がトランザクションの対象となる。\emph{整合性}は、ある値が更新されたときにそれ以降の問い合わせが更新後の値を見られることを保証する。\emph{永続性}は、ある値が更新されたときにそれが安定したストレージ(ハードディスクドライブなど)に書き込まれ、データベースがクラッシュしても復旧可能であることを保証する。

%% NoSQL systems relax some of these guarantees, a decision which, for
%% many non-banking applications, can provide acceptable and predictable
%% behavior in exchange for improved performance.  These relaxations,
%% combined with data model and query language changes, often make it
%% easier to safely partition a database across multiple machines when
%% the data grows beyond a single machine's capability.
NoSQLシステムでは、これらの保証のうちのいくつかをより緩やかにした。金融関連のアプリケーションを除く多くのアプリケーションではそれでも受け入れ可能なレベルであり、保証を緩める引き替えにパフォーマンスを向上させている。このように保証を緩め、そしてデータモデルと問い合わせ言語を変更したことで、データベースをパーティショニングして複数サーバーに分散させることも簡単になった。データの量が増えて一つのマシンではさばききれなくなってもだいじょうぶである。

%% NoSQL systems are still very much in their infancy.  The architectural
%% decisions that go into the systems described in this chapter are a
%% testament to the requirements of various users.  The biggest
%% challenge in summarizing the architectural features of several open
%% source projects is that each one is a moving target.  Keep in mind
%% that the details of individual systems will change. When you pick
%% between NoSQL systems, you can use this chapter to guide your thought
%% process, but not your feature-by-feature product selection.
NoSQLシステムは、まだ生まれたばかりの幼年期にある。本章で取り上げるシステムにおけるアーキテクチャ上の判断は、さまざまなユーザーの要求をとりまとめたものである。さまざまなオープンソースプロジェクトのアーキテクチャをまとめようとしたときに最も大変だったのは、どのシステムも変わりつつあるというところだった。個々のシステムの詳細は変わるものだということを頭に入れておこう。何かのNoSQLシステムを使うことになったときに、本章はどう考えればいいかの指針にはなるだろう。しかし、その製品にどんな機能があるかを知るといった目的には使えない。

%% \pagebreak

%% \noindent As you think about NoSQL systems, here is a roadmap of considerations:
NoSQLシステムについて考えるにあたって、検討すべき点を次にまとめる。

\begin{aosadescription}

  %% \item{Data and query model}: Is your data represented as rows,
  %% objects, data structures, or documents? Can you ask the database to
  %% calculate aggregates over multiple records?
  \item{データモデルとクエリモデル}: データの表現方法は? 行? それともオブジェクト? あるいはデータ構造とかドキュメントとか? データベースに対する問い合わせで複数のレコードを集約できる?

  %% \item{Durability}: When you change a value, does it immediately
  %% go to stable storage?  Does it get stored on multiple machines in
  %% case one crashes?
  \item{永続性}: 値を変更したときに、それはすぐにストレージ上に反映される? ひとつのマシンがクラッシュした場合に備えて複数のマシンに格納する?

  %% \item{Scalability}: Does your data fit on a single server?  Do
  %% the amount of reads and writes require multiple disks to handle the
  %% workload?
  \item{スケーラビリティ}: データは単一のサーバー上に置く? データの読み書きをさばくために複数のディスクを扱う必要がある?

  %% \item{Partitioning}: For scalability, availability, or
  %% durability reasons, does the data need to live on multiple servers?
  %% How do you know which record is on which server?
  \item{パーティショニング}: スケーラビリティや可用性、永続性の観点から、データを複数のサーバーに置く必要がある? どのレコードがどのサーバーにあるのかということをどうやって知る?

  %% \item{Consistency}: If you've partitioned and replicated your
  %% records across multiple servers, how do the servers coordinate when
  %% a record changes?
  \item{整合性}: 複数のサーバーにまたがってデータのパーティショニングや複製を行ったときに、レコードの変更に対して各サーバーはどのように協調する?

  %% \item{Transactional semantics}: When you run a series of
  %% operations, some databases allow you to wrap them in a transaction,
  %% which provides some subset of ACID (Atomicity, Consistency,
  %% Isolation, and Durability) guarantees on the transaction and all
  %% others currently running.  Does your business logic require these
  %% guarantees, which often come with performance tradeoffs?
  \item{トランザクションの特性}: 一連の操作を実行するときに、それをトランザクションとしてまとめることのできるデータベースもある。トランザクションは、実行中の他の操作との間のACID (Atomicity: 原子性、Consistency: 整合性、Isolation: 独立性、Durability: 永続性)の一部あるいはすべてを保証する。これらの保証は一般的にパフォーマンスとのトレードオフとなるが、あなたが扱う業務ロジックはこれらの保証を要するものか?

  %% \item{Single-server performance}: If you want to safely store
  %% data on disk, what on-disk data structures are best-geared toward
  %% read-heavy or write-heavy workloads? Is writing to disk your
  %% bottleneck?
  \item{単一サーバーでのパフォーマンス}: データを安全にディスク上に格納したい場合に、ディスク上でのデータ構造として最適なものは? 読み込みが多い場合と書き込みが多い場合とではどうなる? ディスクへの書き込みがボトルネックになっている?

  %% \item{Analytical workloads}: We're going to pay a lot of
  %% attention to lookup-heavy workloads of the kind you need to run a
  %% responsive user-focused web application.  In many cases, you will
  %% want to build dataset-sized reports, aggregating statistics across
  %% multiple users for example.  Does your use-case and toolchain
  %% require such functionality?
  \item{作業量の分析}: ユーザーにとって使いやすいウェブアプリケーションを作るときには、作業量のチェックに細心の注意を払うことになる。多くの場合、欲しいのはデータセットサイズのレポートで、たとえば複数のユーザーの統計情報を集約したものだろう。あなたの利用法や使うツールは、その手の機能を必要としている?

\end{aosadescription}

%% While we will touch on all of these consideration, the last three, while equally important, see the least attention in this chapter.
これらすべての検討事項について取り上げる予定だが、後半の三点については(どれも同様に重要ではあるけれども)本章ではあまり詳しく扱わない。

\end{aosasect2}

\end{aosasect1}

%% \begin{aosasect1}{NoSQL Data and Query Models}
\begin{aosasect1}{NoSQLのデータモデルおよびクエリモデル}

%% The \emph{data model} of a database specifies how data is logically
%% organized.  Its \emph{query model} dictates how the data can be
%% retrieved and updated.  Common data models are the relational model,
%% key-oriented storage model, or various graph models.  Query languages
%% you might have heard of include SQL, key lookups, and MapReduce.
%% NoSQL systems combine different data and query models, resulting in
%% different architectural considerations.
データベースの\emph{データモデル}とは、データをどのような論理構造で管理するかを示すものである。一方\emph{クエリモデル}は、データの取得や更新をどのように行うのかを決定づける。一般的なデータモデルとしては、関係モデルやキー指向ストレージモデル、そして各種のグラフモデルなどがある。クエリ言語としては、SQLやキールックアップそしてMapReduceなどがおなじみだろう。NoSQLシステムはさまざまなデータモデルとクエリモデルの組み合わせでできており、アーキテクチャ上の検討事項もそれぞれ異なる。

%% \begin{aosasect2}{Key-based NoSQL Data Models}
\begin{aosasect2}{キーベースのNoSQLデータモデル}

%% NoSQL systems often part with the relational model and the full
%% expressivity of SQL by restricting lookups on a dataset to a single
%% field.  For example, even if an employee has many properties, you
%% might only be able to retrieve an employee by her ID\@.  As a result,
%% most queries in NoSQL systems are key lookup-based.  The programmer
%% selects a key to identify each data item, and can, for the most part,
%% only retrieve items by performing a lookup for their key in the
%% database.
NoSQLシステムの多くは、関係モデルやSQLの機能性とは一線を画して、データセットの検索を単一フィールドによるものだけに制限している。たとえば、社員情報にはさまざまな項目があるにもかかわらず、IDによる検索しかできないといった具合だ。その結果として、NoSQLシステムにおける問い合わせの大半は、キーによる検索をベースにしたものとなる。プログラマーは、各データを識別するためのキーを選択する。そしてたいていの場合、できることといえばデータベース内でそのキーによる検索をしてアイテムを取得することくらいなのだ。

%% In key lookup-based systems, complex join operations or multiple-key
%% retrieval of the same data might require creative uses of key names.
%% A programmer wishing to look up an employee by his
%% employee ID and to look up all employees in a department might create
%% two key types.  For example, the key \code{employee:30} would point to an employee
%% record for employee ID 30, and \code{employee\_departments:20} might
%% contain a list of all employees in department 20.  A join operation
%% gets pushed into application logic: to retrieve employees in
%% department 20, an application first retrieves a list of employee IDs
%% from key \code{employee\_departments:20}, and then loops over key
%% lookups for each \code{employee:ID} in the employee list.
キールックアップ方式のシステムでは、複雑な結合操作や複数キーによる同一データの取得などを実現しようとすると、キーの名前にちょっとした工夫を要する。社員を検索する際に「社員IDでの検索」「ある部署に所属する全社員の検索」の二通りを行いたい場合は、二種類のキーを作成することになる。たとえば、キー\code{employee:30}は社員IDが30の社員レコードを指し、キー\code{employee\_departments:20}は部署番号20に属する全社員のリストを含むといった具合だ。結合操作はアプリケーションのロジック側に追い出される。部署番号20に属する全社員を取得するには、アプリケーション側でまず\code{employee\_departments:20}を使って社員IDのリストを取得し、そのリストをループさせて各IDに対して\code{employee:ID}による検索を行う。

%% The key lookup model is beneficial because it means that the database
%% has a consistent query pattern---the entire workload consists of key
%% lookups whose performance is relatively uniform and predictable.
%% Profiling to find the slow parts of an application is simpler, since
%% all complex operations reside in the application code.  On the flip
%% side, the data model logic and business logic are now more closely
%% intertwined, which muddles abstraction.
キールックアップモデルの利点は、データベースへの問い合わせのパターンが一貫したものになるというところである。データベースで行う作業はキールックアップだけであり、これは比較的一様で予測しやすいものである。アプリケーションのボトルネックを探すプロファイリングもシンプルになる。というのも、複雑な操作はアプリケーションのコード側に押し出されているからである。その反面、データモデルのロジックと業務ロジックが密結合してしまい、抽象化は崩れてしまう。

%% Let's quickly touch on the data associated with each key.  Various
%% NoSQL systems offer different solutions in this space.
各キーに関連づけられたデータについて見ていこう。各種NoSQLシステムは、さまざまなソリューションを使っている。

%% \begin{aosasect3}{Key-Value Stores}
\begin{aosasect3}{キー・バリュー ストア}

%% The simplest form of NoSQL store is a \emph{key-value} store.  Each
%% key is mapped to a value containing arbitrary data.  The NoSQL store
%% has no knowledge of the contents of its payload, and simply delivers
%% the data to the application.  In our Employee database example, one
%% might map the key \code{employee:30} to a blob containing JSON or a
%% binary format such as Protocol
%% Buffers\footnote{\url{http://code.google.com/p/protobuf/}},
%% Thrift\footnote{\url{http://thrift.apache.org/}}, or
%% Avro\footnote{\url{http://avro.apache.org/}} in order to encapsulate
%% the information about employee 30.
NoSQLのデータ格納方式の中で最もシンプルなのが\emph{キー・バリュー}ストアだ。個々のキーを、任意のデータを含む値に対応させる。NoSQLシステム自体はその値の中身については何も知らず、単にデータをアプリケーションに渡すだけとなる。先ほどの社員データベースの例で考えると、キー\code{employee:30}をblobに対応させることになる。その中身はJSONかもしれないし、Protocol Buffers\footnote{\url{http://code.google.com/p/protobuf/}}やThrift\footnote{\url{http://thrift.apache.org/}}あるいはAvro\footnote{\url{http://avro.apache.org/}}のようなバイナリフォーマットかもしれない。何らかの形式で、社員IDが30の社員の情報をカプセル化したものとなる。

%% If a developer uses structured formats to store complex data for a
%% key, she must operate against the data in application space: a
%% key-value data store generally offers no mechanisms for querying for
%% keys based on some property of their values.  Key-value stores shine
%% in the simplicity of their query model, usually consisting of
%% \code{set}, \code{get}, and \code{delete} primitives, but discard the
%% ability to add simple in-database filtering capabilities due to the
%% opacity of their values.  Voldemort, which is based on Amazon's
%% Dynamo, provides a distributed key-value store.  BDB\footnote{\url{http://www.oracle.com/technetwork/database/berkeleydb/overview/index.html}} offers a
%% persistence library that has a key-value interface.
構造化されたフォーマットで複雑なデータを表してそれをキーに関連づけた場合は、取り出したデータの処理はアプリケーション側で行う必要がある。キー・バリュー形式のデータストアでは、キーを指定して取り出した価の中の特定の項目を取り出すような仕組みは用意されていない。キー・バリューストアの強みは、そのシンプルなクエリモデルにある。通常は\code{set}、\code{get}そして\code{delete}といったプリミティブで構成されている。一方、データベース内でのシンプルな絞り込み機能を追加する仕組みは持っていない。これは、扱うデータの中身が把握できないからである。VoldemortはAmazonのDynamoをベースにしたシステムであり、分散型キー・バリューストアを提供する。BDB\footnote{\url{http://www.oracle.com/technetwork/database/berkeleydb/overview/index.html}}は、キー・バリュー型のインターフェイスを持つ永続化ライブラリを提供する。

\end{aosasect3}

%% \begin{aosasect3}{Key-Data Structure Stores}
\begin{aosasect3}{キー・データ構造 ストア}

%% Key-data structure stores, made popular by Redis\footnote{\url{http://redis.io/}}, assign each value a
%% type.  In Redis, the available types a value can take on are integer,
%% string, list, set, and sorted set.  In addition to
%% \code{set}/\code{get}/\code{delete}, type-specific commands, such as
%% increment/decrement for integers, or push/pop for lists, add
%% functionality to the query model without drastically affecting
%% performance characteristics of requests.  By providing simple
%% type-specific functionality while avoiding multi-key operations such as
%% aggregation or joins, Redis balances functionality and performance.
キー・データ構造 ストアはRedis\footnote{\url{http://redis.io/}}によって有名になった方式で、値として型を割り当てる。Redisでは、値として使える型はinteger、string、list、setそしてsorted setである。\code{set}/\code{get}/\code{delete}に加えて型ごとに固有のコマンドも用意されている。たとえば整数型ならインクリメントやデクリメント、リストならプッシュやポップなどだ。さらに、クエリモデルにも機能が追加されている。リクエストの種類によってパフォーマンスが劇的に落ちるなどということはない。シンプルな、型ごとの機能を提供する一方で、集約や結合といった複数キーの操作はできない。このようにして、Redisは機能とパフォーマンスのバランスをとっている。

\end{aosasect3}

%% \begin{aosasect3}{Key-Document Stores}
\begin{aosasect3}{キー・ドキュメント ストア}

%% Key-document stores, such as CouchDB\footnote{\url{http://couchdb.apache.org/}}, MongoDB\footnote{\url{http://www.mongodb.org/}}, and Riak\footnote{\url{http://www.basho.com/products_riak_overview.php}}, map a key to
%% some document that contains structured information.  These systems
%% store documents in a JSON or JSON-like format.  They store lists and
%% dictionaries, which can be embedded recursively inside one-another.
キー・ドキュメント ストアにはCouchDB\footnote{\url{http://couchdb.apache.org/}}、MongoDB\footnote{\url{http://www.mongodb.org/}}そしてRiak\footnote{\url{http://www.basho.com/products_riak_overview.php}}などがある。これらは、構造化された情報を含むドキュメントをキーにマップする。これらのシステムは、ドキュメントをJSON形式(あるいはその類似形式)で格納する。リストや辞書も格納し、あるドキュメントの中に別のドキュメントを再帰的に埋め込むこともできる。

%% MongoDB separates the keyspace into collections, so that keys for
%% Employees and Department, for example, do not collide.  CouchDB and
%% Riak leave type-tracking to the developer.  The freedom and complexity
%% of document stores is a double-edged sword: application developers
%% have a lot of freedom in modeling their documents, but
%% application-based query logic can become exceedingly complex.
MongoDBはキー空間をコレクション内で分離しているので、たとえばEmployeesのキーとDepartmentのキーが衝突することはない。CouchDBやRiakは、型の追跡を開発者側に任せている。ドキュメントの格納方法の自由さと複雑さは諸刃の剣である。アプリケーションの開発者はドキュメントのモデリングに関してかなりの自由を与えられているが、アプリケーション側での問い合わせのロジックは著しく複雑化する。

\end{aosasect3}

%% \begin{aosasect3}{BigTable Column Family Stores}
\begin{aosasect3}{BigTableカラムファミリー ストア}

%% HBase and Cassandra base their data model on the one used by Google's
%% BigTable.  In this model, a key identifies a row, which contains data
%% stored in one or more Column Families (CFs).  Within a CF, each row
%% can contain multiple columns.  The values within each column are
%% timestamped, so that several versions of a row-column mapping can live
%% within a CF.
HBaseやCassandraは、GoogleのBigTableが使っているモデルをベースにしたデータモデルを採用している。このモデルでは、キーがひとつの行を指し示す。その行に含まれるデータは、ひとつあるいは複数のカラムファミリー(CF)に格納されている。CFの中で、各行は複数の列を保持できる。列内の値にはタイムスタンプがついており、複数のバージョンの行・列マッピングを一つのCFに保持することができる。

%% Conceptually, one can think of Column Families as storing complex keys
%% of the form (row~ID, CF, column, timestamp), mapping to values which
%% are sorted by their keys.  This design results in data modeling
%% decisions which push a lot of functionality into the keyspace.  It is
%% particularly good at modeling historical data with timestamps.  The
%% model naturally supports sparse column placement since row~IDs that do
%% not have certain columns do not need an explicit NULL value for those
%% columns.  On the flip side, columns which have few or no NULL values
%% must still store the column identifier with each row, which leads to
%% greater space consumption.
概念的には、カラムファミリーを次のようにとらえることができる。つまり、ある形式(行ID、CF、列、タイムスタンプ)の複合キーを格納し、それをキーで並べ替えた複数の値にマップするというものだ。この設計が、多くの機能をキー空間に持たせるというデータモデリングにつながる。この方式は、タイムスタンプを持つヒストリカルなデータのモデリングに適している。もちろん、このモデルはスパース列に対応している。というのも、何も列を持たない行IDが、必ずしも各列にNULL値を持つ必要がないからである。その反面、NULL値をほとんど(あるいはまったく)持たない列でも各行に列IDが必要となる。そのため、要する領域は多くなる。

%% Each project data model differs from the original BigTable model in
%% various ways, but Cassandra's changes are most notable.  Cassandra
%% introduces the notion of a supercolumn within each CF to allow for
%% another level of mapping, modeling, and indexing.  It also does away
%% with a notion of locality groups, which can physically store multiple
%% column families together for performance reasons.
どのプロジェクトのデータモデルもオリジナルのBigTableのモデルとはいろいろな面で異なるが、中でも特筆すべきなのがCassandraにおける変更だろう。Cassandraは、各CFの中にスーパーカラムという概念を導入した。スーパーカラムを使って、違ったレベルでのマッピングやモデリングそしてインデキシングを行えるようにしたのである。また、複数のカラムファミリーをひとまとめに格納してパフォーマンスを稼ぐ仕組みであるローカルグループという概念を廃止した。

\end{aosasect3}

\end{aosasect2}

%% \begin{aosasect2}{Graph Storage}
\begin{aosasect2}{グラフストレージ}

%% One class of NoSQL stores are graph stores.  Not all data is created
%% equal, and the relational and key-oriented data models of storing and
%% querying data are not the best for all data.  Graphs are a fundamental
%% data structure in computer science, and systems such as HyperGraphDB\footnote{\url{http://www.hypergraphdb.org/index}}
%% and Neo4J\footnote{\url{http://neo4j.org/}} are two popular NoSQL storage systems for storing
%% graph-structured data.  Graph stores differ from the other stores we
%% have discussed thus far in almost every way: data models, data
%% traversal and querying patterns, physical layout of data on disk,
%% distribution to multiple machines, and the transactional semantics of
%% queries.  We can not do these stark differences justice given space
%% limitations, but you should be aware that certain classes of data may
%% be better stored and queried as a graph.
NoSQLのデータ格納方式のひとつに、グラフストレージがある。データを作る方法はただ一つとは限らないし、リレーショナルモデルやキー指向のモデルがデータの格納や問い合わせに対して常に最適であるとは限らない。グラフは計算機科学では基本的なデータ構造であり、HyperGraphDB\footnote{\url{http://www.hypergraphdb.org/index}}やNeo4J\footnote{\url{http://neo4j.org/}}はグラフ構造のデータを格納するNoSQLストレージシステムとしてよく知られている。グラフストレージは、これまで取り上げた他のストレージとはあらゆる点で異なる。データモデル、データの走査や問い合わせのパターン、ディスク上での物理的なデータ配置、複数マシンへの分散、クエリのトランザクション特性などがすべて異なるのだ。このように全く異なるものを公正に評価するにはページが足りない。しかし、これだけは意識しておこう。ある種のデータに関しては、グラフとして格納したほうがずっとうまく扱えるということを。

\end{aosasect2}

%% \begin{aosasect2}{Complex Queries}
\begin{aosasect2}{複雑な問い合わせ}

%% There are notable exceptions to key-only lookups in NoSQL systems.
%% MongoDB allows you to index your data based on any number of
%% properties and has a relatively high-level language for specifying
%% which data you want to retrieve.  BigTable-based systems support
%% scanners to iterate over a column family and select particular items by a
%% filter on a column.  CouchDB allows you to create different views of
%% the data, and to run MapReduce tasks across your table to facilitate
%% more complex lookups and updates.  Most of the systems have bindings
%% to Hadoop or another MapReduce framework to perform dataset-scale
%% analytical queries.
NoSQLシステムにおけるキーだけを使ったルックアップには、特筆すべき例外がある。MongoDBでは任意の数のプロパティを使った索引付けができるようになっており、比較的高レベルの問い合わせ言語を使って取得したいデータを指定することもできる。BigTableベースのシステムでは、スキャナーを使ったカラムファミリーの反復処理に対応しており、特定のアイテムを洗濯する際に、カラム上での絞り込みができる。CouchDBではデータに対してさまざまなビューを作ることができ、テーブルに対してMapReduceタスクを実行させ、より複雑なルックアップや更新もできるようにしている。ほとんどのシステムにはHadoopあるいはその他のMapReduceフレームワークへのバインディングがあり、データセットに対して解析的な問い合わせを実行できる。

\end{aosasect2}

%% \begin{aosasect2}{Transactions}
\begin{aosasect2}{トランザクション}

%% NoSQL systems generally prioritize performance over
%% \emph{transactional semantics}.  Other SQL-based systems allow any set
%% of statements---from a simple primary key row retrieval, to a
%% complicated join between several tables which is then subsequently
%% averaged across several fields---to be placed in a transaction.
NoSQLシステムは全般的に、\emph{トランザクションの特性}よりもパフォーマンスを重視している。SQLベースのシステムでは、複数の文の組み合わせ---主キーを指定して行を取得するといった単純な処理から、複数のテーブルを連結していくつかのフィールドの平均を算出するなどの複雑な処理まで---をひとつのトランザクションにまとめられるようになっている。

%% These SQL databases will offer ACID guarantees between transactions.
%% Running multiple operations in a transaction is Atomic (the A in
%% ACID), meaning all or none of the operations happen.  Consistency (the
%% C) ensures that the transaction leaves the database in a consistent,
%% uncorrupted state.  Isolation (the I) makes sure that if two
%% transactions touch the same record, they will do without stepping on
%% each other's feet.  Durability (the D, covered extensively in the next
%% section), ensures that once a transaction is committed, it's stored in
%% a safe place.
SQLデータベースは、トランザクション間でのACIDを保証している。複数の操作をひとまとめにして実行するトランザクションは原子性(Atomic: ACIDのA)がある。つまり、すべての操作が行われるか、なにも行われないかのいずれかになる。整合性(Consistency: ACIDのC)が保証するのは、そのトランザクションがデータベースの一貫性を保ち、状態を破壊しないということだ。独立性(Isolation: ACIDのI)とは、二つのトランザクションが同時に同じレコードを操作したとしてもお互い相手側に影響を及ぼさないということである。永続性(Durability: ACIDのD、次の節で詳述する)が保証するのは、トランザクションが確定したらそれが安全な場所に格納されるということだ。

%% ACID-compliant transactions keep developers sane by making it easy to
%% reason about the state of their data.  Imagine multiple
%% transactions, each of which has multiple steps (e.g., first check the
%% value of a bank account, then subtract \$60, then update the
%% value). ACID-compliant databases often are limited in how they can
%% interleave these steps while still providing a correct result across
%% all transactions.  This push for correctness results in
%% often-unexpected performance characteristics, where a slow transaction
%% might cause an otherwise quick one to wait in line.
ACID準拠のトランザクションは、開発者に安心を与えてくれる。データの状態の確認が容易になるからだ。こんな場面を想像してみよう。複数のトランザクションが並行稼働しており、それぞれが複数のステップからなる処理をしている(たとえば、まず銀行口座の残高を確認してその次に\$60を引き落とし、最後に値を更新するなど)。ACID準拠のデータベースはこれらの処理順序に関して何らかの制限がかかることが多いが、すべてのトランザクションで正しい結果が得られる。正確さを重視した結果、パフォーマンス特性に予期せぬ影響が出ることが多い。処理が遅いトランザクションが一つあるせいで、他のトランザクションもそれにあわせて処理を待つ羽目になるといったものだ。

%% Most NoSQL systems pick performance over full ACID guarantees, but do
%% provide guarantees at the key level: two operations on the same key
%% will be serialized, avoiding serious corruption to key-value pairs.
%% For many applications, this decision will not pose noticeable
%% correctness issues, and will allow quick operations to execute with
%% more regularity.  It does, however, leave more considerations for
%% application design and correctness in the hands of the developer.
大半のNoSQLシステムは、ACIDに完全に準拠することよりもパフォーマンスを向上させることを優先している。しかし、キーのレベルではACIDを保証しており、同じキーに対する二つの操作があればそれは直列化され、キーと値のペアに深刻な被害が及ばないようにしている。多くのアプリケーションではこのレベルで十分で、データの正確性に目立った問題が発生することもない。また、より規則性のある操作を素早く実行できるようになる。しかしこの方針のおかげで、アプリケーションの設計やデータの正確性に関して開発者側で考慮しなければならない点はより多くなる。

%% Redis is the notable exception to the no-transaction trend.  On a
%% single server, it provides a \code{MULTI} command to combine multiple
%% operations atomically and consistently, and a \code{WATCH} command to
%% allow isolation.  Other systems provide lower-level
%% \emph{test-and-set} functionality which provides some isolation
%% guarantees.
トランザクションを軽視する傾向に反する例外として特筆すべきなのがRedisだ。単一サーバー上で、Redisは\code{MULTI}コマンドを提供する。これは、原子性と整合性を保証した状態で複数の操作を組み合わせて実行するものだ。また\code{WATCH}コマンドは独立性を保証する。それ以外のシステムでは、より低レベルな\emph{test-and-set}\footnote{[訳注]「更新前に確かめる」}機能を提供しており、これで同様の独立性を保証している。

\end{aosasect2}

%% \begin{aosasect2}{Schema-free Storage }
\begin{aosasect2}{スキーマフリー ストレージ}

%% A cross-cutting property of many NoSQL systems is the lack of schema
%% enforcement in the database.  Even in document stores and column
%% family-oriented stores, properties across similar entities are not
%% required to be the same.  This has the benefit of supporting less
%% structured data requirements and requiring less performance expense
%% when modifying schemas on-the-fly.  The decision leaves more
%% responsibility to the application developer, who now has to program
%% more defensively.  For example, is the lack of a \code{lastname}
%% property on an employee record an error to be rectified, or a schema
%% update which is currently propagating through the system?  Data and
%% schema versioning is common in application-level code after a few
%% iterations of a project which relies on \emph{sloppy-schema} NoSQL
%% systems.
多くのNoSQLシステムに共通する特徴が、データベース内でスキーマを強要しないということである。ドキュメントやカラムファミリーを格納する方式であっても、各エンティティのプロパティが同じである必要はない。その利点は、構造化されたデータに関してサポートすべき要件が減るということ。そして、スキーマをオンザフライで修正するときにもパフォーマンスの劣化はあまり起こらないということである。そのぶん、アプリケーションの開発者側にはより多くの責務が課せられる。より身構えたプログラムが必要になるのだ。たとえば、社員レコードに\code{lastname}プロパティがなかったとして、それは修正すべきエラーなのだろうか。それとも、スキーマの更新がシステムを通じて伝搬している最中なのだろうか。\emph{sloppy-schema}なNoSQLシステムを使うプロジェクトの場合、数回のイテレーションを終えた後のデータやスキーマのバージョン管理は、アプリケーションレベルのコードで行うことになる。

\end{aosasect2}

\end{aosasect1}

%% \begin{aosasect1}{Data Durability}
\begin{aosasect1}{データの永続性}

%% Ideally, all data modifications on a storage system would immediately
%% be safely persisted and replicated to multiple locations to avoid data
%% loss.  However, ensuring data safety is in tension with performance,
%% and different NoSQL systems make different \emph{data durability}
%% guarantees in order to improve performance.  Failure scenarios are
%% varied and numerous, and not all NoSQL systems protect you against
%% these issues.
理想を言えば、データに何か変更があったときにはそれをすぐに安全な場所に永続化させたいし、複数の場所にレプリカを作るなどしてデータのロスを防ぎたい。しかし、データの安全性を保証しようとするとパフォーマンスに影響が及ぶ。そこで、各種NoSQLシステムはそれとは異なる手法で\emph{データの永続性}を保証しつつパフォーマンスを向上させている。データを失う場面にはさまざまなものがあるし、すべてのNoSQLシステムがこういった問題からあなたを守ってくれるというわけでもない。

%% A simple and common failure scenario is a server restart or power
%% loss.  Data durability in this case involves having moved the data
%% from memory to a hard disk, which does not require power to store
%% data.  Hard disk failure is handled by copying the data to secondary
%% devices, be they other hard drives in the same machine (RAID
%% mirroring) or other machines on the network.  However, a data center
%% might not survive an event which causes correlated failure (a tornado, for example), and some
%% organizations go so far as to copy data to backups in data centers
%% several hurricane widths apart. Writing to hard drives and copying
%% data to multiple servers or data centers is expensive, so different
%% NoSQL systems trade off durability guarantees for performance.
いちばんシンプルかつありがちなシナリオは、サーバーの再起動や停電などだ。このような場合を想定してデータの永続性を確保するには、データをメモリからハードディスクに移すことになる。ハードディスクは、電源を落としてもデータを失わない。ハードディスク障害に対応するには、データを別のデバイスにコピーする。コピー先は、同一マシン上の別のハードディスク(RAIDミラー)だったりネットワーク上の別のマシンだったりする。しかし、データセンターも、ハリケーンなどの自然災害にあえば使えなくなる可能性がある。そこで、ひとつのハリケーンで同時に被害にあうことのない程度に離れた場所にあるデータセンターにバックアップを取るという組織も存在する。データをハードディスクに書き込んで複数のサーバーやデータセンターにコピーするという作業は高くつく。そこで、さまざまなNoSQLシステムはデータの永続性の保証とパフォーマンスを天秤にかけてバランスを取っている。

%% \begin{aosasect2}{Single-server Durability}
\begin{aosasect2}{単一サーバーの永続化}

%% The simplest form of durability is a \emph{single-server durability},
%% which ensures that any data modification will survive a server restart
%% or power loss.  This usually means writing the changed data to disk,
%% which often bottlenecks your workload.  Even if you order your
%% operating system to write data to an on-disk file, the operating
%% system may buffer the write, avoiding an immediate modification on
%% disk so that it can group several writes together into a single
%% operation.  Only when the \code{fsync} system call is issued does the
%% operating system make a best-effort attempt to ensure that buffered
%% updates are persisted to disk.
永続化の型として最もシンプルなのが\emph{単一サーバーの永続化}で、サーバーを再起動したり電源を落としたりしても変更したデータが生き残ることを保証する。通常これは、変更したデータをディスクに書き込むことを意味する。そしてこの処理がボトルネックになることが多い。ディスク上のファイルにデータを書き込むようOSに指示を出したとしても、OSは書き込みをバッファリングしてすぐには書き込まないことがある。複数の書き込み操作を一括処理するためである。\code{fsync}システムコールを実行すれば、バッファにたまった更新をOSディスクに永続化させようと試みる。

%% Typical hard drives can perform 100-200 random accesses (seeks) per
%% second, and are limited to 30-100 MB/sec of sequential writes.  Memory can be orders of magnitudes faster in both scenarios.  Ensuring
%% efficient single-server durability means limiting the number of random
%% writes your system incurs, and increasing the number of sequential
%% writes per hard drive. Ideally, you want a system to minimize the
%% number of writes between \code{fsync} calls, maximizing the number of
%% those writes that are sequential, all the while never telling the user
%% their data has been successfully written to disk until that write has
%% been \code{fsync}ed.  Let's cover a few techniques for improving
%% performance of single-server durability guarantees.
一般的なハードディスクドライブの性能は、一秒あたり100から200のランダムアクセス(シーク)といったものであり、シーケンシャルライトもたかだか30-100 MB/sec程度である。どちらについても、メモリのほうが桁違いに高速である。単一サーバーでの永続化を保証する効率を上げるには、あなたのシステムによるランダムライトの回数を減らし、ハードディスクごとのシーケンシャルライトの回数を増やすようにすればよい。理想的には、一回の\code{fsync}コールあたりの書き込み回数を最小化してシーケンシャルライトの回数を最大化したいものだ。そして、書き込みを\code{fsync}させるまではユーザーに対して書き込み成功を伝えないようにしておきたい。単一サーバーでの永続化を保証するときにパフォーマンスを改善するためのテクニックを、いくつか紹介する。

%% \begin{aosasect3}{Control \code{fsync} Frequency}
\begin{aosasect3}{\code{fsync}の頻度の制御}

%% Memcached\footnote{\url{http://memcached.org/}} is an example of a system which offers no on-disk durability
%% in exchange for extremely fast in-memory operations.  When a server
%% restarts, the data on that server is gone: this makes for a good cache
%% and a poor durable data store.
Memcached\footnote{\url{http://memcached.org/}}は、ディスク上での永続化の保障を放棄する引き換えとして、極めて高速なインメモリでの操作を提供するシステムのひとつである。サーバーを再起動すると、memcached上のデータは消えてしまう。つまり、キャッシュとしてはよくできているが永続化には難があるデータストアとなる。

%% Redis offers developers several options for when to call
%% \code{fsync}. Developers can force an \code{fsync} call after every
%% update, which is the slow and safe choice.  For better performance,
%% Redis can \code{fsync} its writes every N seconds.  In a worst-case
%% scenario, the you will lose last N seconds worth of operations, which
%% may be acceptable for certain uses.  Finally, for use cases where
%% durability is not important (maintaining coarse-grained statistics, or
%% using Redis as a cache), the developer can turn off \code{fsync} calls
%% entirely: the operating system will eventually flush the data to disk,
%% but without guarantees of when this will happen.
Redisの場合は、どのタイミングで\code{fsync}をコールするかについていくつかのオプションを選べるようになっている。更新のたびに\code{fsync}をコールするような設定もできる。これは、低速だが安全な選択肢となる。よりパフォーマンスを稼ぐために、N秒おきに書き込みを\code{fsync}させることも可能だ。この場合、最悪でN秒ぶんの操作をロストしてしまうことになるが、その程度なら受け入れられるという使い方もあるだろう。最後に、永続化を重視しないような場面(おおざっぱな統計情報の保守や、Redisをキャッシュとして使うといった場面)では、\code{fsync}をまったくコールしないようにもできる。適当なタイミングでOSがデータをディスクに書き込むだろうが、それがいつ発生するかはまったく保証しないという選択肢だ。

\end{aosasect3}

%% \begin{aosasect3}{Increase Sequential Writes by Logging}
\begin{aosasect3}{ログ出力によるシーケンシャルライトの増加}

%% Several data structures, such as B+Trees, help NoSQL systems quickly
%% retrieve data from disk.  Updates to those structures result in
%% updates in random locations in the data structures' files, resulting
%% in several random writes per update if you \code{fsync} after each
%% update.  To reduce random writes, systems such as Cassandra, HBase,
%% Redis, and Riak append update operations to a sequentially-written
%% file called a \emph{log}.  While other data structures used by the
%% system are only periodically \code{fsync}ed, the log is frequently
%% \code{fsync}ed.  By treating the log as the ground-truth state of the
%% database after a crash, these storage engines are able to turn random
%% updates into sequential ones.
NoSQLシステムがディスクから高速にデータを取得するために、B+木などのデータ構造が使われている。こういったデータ構造のデータを更新するときには、ファイル内のランダムな場所を更新する。更新のたびに\code{fsync}しようとすると、一回の更新に対して複数のランダムライトが発生することになる。ランダムライトを減らすために、CassandraやHBase、Redis、そしてRiakといったシステムは、更新操作を\emph{log}というファイルにシーケンシャルに書き込んでいる。システムで使っている他のデータ構造は言っての期間ごとに\code{fsync}するのに対して、ログだけは頻繁に\code{fsync}を行う。データベースがクラッシュしたときにはログを正式な状態として扱うことで、ランダムな更新をシーケンシャルライトにまとめている。

%% While NoSQL systems such as MongoDB perform writes in-place in their
%% data structures, others take logging even further.  Cassandra and
%% HBase use a technique borrowed from BigTable of combining their logs
%% and lookup data structures into one \emph{log-structured merge tree}.
%% Riak provides similar functionality with a \emph{log-structured hash
%% table}.  CouchDB has modified the traditional B+Tree so that all
%% changes to the data structure are appended to the structure on
%% physical storage.  These techniques result in improved write
%% throughput, but require a periodic log compaction to keep the log from
%% growing unbounded.
NoSQLシステムの中には、MongoDBのようにその場でデータ構造に書き込みを行うものもあれば、さらにロギングを行うものもある。CassandraやHBaseが使っているテクニックはBigTableを参考にしたもので、ログとルックアップデータ構造をひとつの\emph{log-structured merge tree}にまとめている。Riakは、同党の機能を\emph{log-structured hash table}で提供する。CouchDBは伝統的なB+木に手を加えたものを使っており、すべての変更を物理ストレージ上の構造に追記する。これらのテクニックによって書き込みのスループットは向上するが、定期的にログの最適化をしないとログのサイズがどんどん膨れ上がってしまう。

\end{aosasect3}

%% \begin{aosasect3}{Increase Throughput by Grouping Writes}
\begin{aosasect3}{書き込みのグルーピングによるスループットの向上}

%% Cassandra groups multiple concurrent updates within a short window
%% into a single \code{fsync} call.  This design, called \emph{group
%% commit}, results in higher latency per update, as users have to wait
%% on several concurrent updates to have their own update be
%% acknowledged.  The latency bump comes at an increase in throughput, as
%% multiple log appends can happen with a single \code{fsync}.  As of
%% this writing, every HBase update is persisted to the underlying
%% storage provided by the Hadoop Distributed File System
%% (HDFS)\footnote{\url{http://hadoop.apache.org/hdfs/}}, which has
%% recently seen patches to allow support of appends that respect
%% \code{fsync} and group commit.
Cassandraは、複数の更新を並行してまとめ、一回の\code{fsync}コールの間に実行する。このような設計は\emph{グループコミット}と呼ばれており、更新あたりの待ち時間が長くなってしまう。ユーザーによる更新が受け付けられたかどうかを知るには、並行するいくつかの更新が完了するまで待たなければならない。待ち時間が増える一方で、これはスループットの向上につながる。複数のログ追記処理が一回の\code{fsync}で処理されるからだ。本章の執筆時点では、HBaseの更新はHadoop Distributed File System (HDFS)\footnote{\url{http://hadoop.apache.org/hdfs/}}が提供するストレージに永続化される。最近適用されたパッチで、\code{fsync}やグループコミットを尊重する追記もサポートするようになった。

\end{aosasect3}

\end{aosasect2}

%% \begin{aosasect2}{Multi-server Durability}
\begin{aosasect2}{複数サーバーの永続化}

%% Because hard drives and machines often irreparably fail, copying
%% important data across machines is necessary.  Many NoSQL systems offer
%% multi-server durability for data.
ハードディスクドライブだってマシンだって、壊れてしまって復旧不能になることがある。重要なデータは別のマシンにもコピーしておくことが必須である。多くのNoSQLシステムには、複数のサーバーを使ってデータを永続化する仕組みが存在する。

%% Redis takes a traditional master-slave approach to replicating data.
%% All operations executed against a master are communicated in a
%% log-like fashion to slave machines, which replicate the operations on
%% their own hardware.  If a master fails, a slave can step in and serve
%% the data from the state of the operation log that it received from the
%% master.  This configuration might result in some data loss, as the
%% master does not confirm that the slave has persisted an operation in
%% its log before acknowledging the operation to the user.  CouchDB
%% facilitates a similar form of directional replication, where servers
%% can be configured to replicate changes to documents on other stores.
Redisは、伝統的なマスター/スレーブ型の手法でデータを複製する。マスターに対してなされたすべての操作がログ風の仕組みでスレーブ機に送られ、スレーブ機の上で同じ操作を再現させる。マスター上で障害が発生したら、マスターから受け取ったオペレーションログの状態に基づいてスレーブがデータを提供することになる。この構成では、何らかのデータロスが発生する可能性がある。マスターへの更新の結果をユーザーに返す前に、スレーブ上へのログの永続化が完了したかどうかを確認しないからである。CouchDBは、同様の形式で双方向のレプリケーションを行う。ドキュメントに対する変更を他のマシンに複製するよう、サーバーを設定するのだ。

%% MongoDB provides the notion of replica sets, where some number of
%% servers are responsible for storing each document.  MongoDB gives
%% developers the option of ensuring that all replicas have received
%% updates, or to proceed without ensuring that replicas have the most
%% recent data.  Many of the other distributed NoSQL storage systems
%% support multi-server replication of data.  HBase, which is built on
%% top of HDFS, receives multi-server durability through HDFS\@.  All
%% writes are replicated to two or more HDFS nodes before returning
%% control to the user, ensuring multi-server durability.
MongoDBにはレプリカセットという仕組みがあり、何台かのサーバーで各ドキュメントの格納にかかわる。MongoDBのオプションで、すべてのレプリカが更新を受け取ったことを保証させることもできる。一方、最新のデータがすべてのレプリカに行きわたるのを確認せずに処理を進めることもできる。その他多くの分散型NoSQLストレージシステムは、データのマルチサーバーレプリケーションに対応している。HDFS上に構築されるHBaseは、複数サーバーの永続化をHDFS経由で実現する。すべての書き込みは、ふたつ以上のHDFSノードに複製されるまでユーザーに制御を返さない。これによって、複数サーバーでの永続化を保証している。

%% Riak, Cassandra, and Voldemort support more configurable forms of
%% replication.  With subtle differences, all three systems allow the
%% user to specify \code{N}, the number of machines which should
%% ultimately have a copy of the data, and \code{W}{\textless}\code{N},
%% the number of machines that should confirm the data has been written
%% before returning control to the user.
RiakやCassandraそしてVoldemortでは、より細やかにレプリケーションを設定できる。それぞれ微妙な違いはあるが、これらのシステムでは\code{N}と\code{W}のふたつの値を設定できる。\code{N}は最終的にデータのコピーを保持することになるマシンの台数、そして\code{W}は\code{W}{\textless}\code{N}を満たす数で、少なくともこれだけの台数のマシンにデータが書き込まれた時点でユーザーに制御を戻す。

%% To handle cases where an entire data center goes out of service,
%% multi-server replication across data centers is required.  Cassandra,
%% HBase, and Voldemort have \emph{rack-aware} configurations, which
%% specify the rack or data center in which various machines are located.
%% In general, blocking the user's request until a remote server has
%% acknowledged an update incurs too much latency. Updates are streamed
%% without confirmation when performed across wide area networks to
%% backup data centers.
データセンター全体のサービスが停止してしまう事態に対応するには、複数のデータセンターにまたがるマルチサーバーのレプリケーションが必要になる。CassandraやHBaseそしてVoldemortには\emph{rack-aware}な設定があり、さまざまなマシンがどのラック(あるいはどのデータセンター)に配置されているのかを指定することができる。一般に、リモートサーバーでの処理が完了するまでユーザーのリクエストをブロックすると、待ち時間が長くなってしまう。そこで、WANによる別のデータセンターへのバックアップのときは、処理の完了を確認せずに更新処理を終える。

\end{aosasect2}

\end{aosasect1}

%% \begin{aosasect1}{Scaling for Performance}
\begin{aosasect1}{パフォーマンス向上のためのスケーリング}

%% Having just spoken about handling failure, let's imagine a rosier
%% situation: success!  If the system you build reaches success, your
%% data store will be one of the components to feel stress under load.  A
%% cheap and dirty solution to such problems is to \emph{scale up} your
%% existing machinery: invest in more RAM and disks to handle the
%% workload on one machine.  With more success, pouring money into more
%% expensive hardware will become infeasible.  At this point, you will
%% have to replicate data and spread requests across multiple machines to
%% distribute load.  This approach is called \emph{scale out}, and is
%% measured by the \emph{horizontal scalability} of your system.
エラー処理について語る前に、もっと楽観的な状況を考えてみよう。やった!大成功!という場面だ。あなたが構築したシステムがうまく動き出すと、データストアはそのコンポーネントのひとつとなり、それなりの負荷にさらされることになる。お手軽だがあまり美しくない解決策は、既存の機器を\emph{スケールアップ}することだ。RAMとディスクをさらに調達して、ひとつのマシンでさばける量を増やせばよい。あなたのシステムがさらに成功を収めると、ハードウェアをよいものにして高価なメモリをどんどん投入することにも限界が出てくる。ここまでくると、データをレプリケートして複数マシンで負荷分散をさせるしか方法がなくなる。これは\emph{スケールアウト}とよばれる手法で、システムの\emph{水平スケーラビリティ}の指標となる。

%% The ideal horizontal scalability goal is \emph{linear scalability}, in
%% which doubling the number of machines in your storage system doubles
%% the query capacity of the system.  The key to such scalability is in
%% how the data is spread across machines.  Sharding is the act of
%% splitting your read and write workload across multiple machines to
%% scale out your storage system.  Sharding is fundamental to the design
%% of many systems, namely Cassandra, HBase, Voldemort, and Riak, and
%% more recently MongoDB and Redis.  Some projects such as CouchDB focus
%% on single-server performance and do not provide an in-system solution
%% to sharding, but secondary projects provide coordinators to partition
%% the workload across independent installations on multiple machines.
水平スケーラビリティの理想的な目標は\emph{リニアなスケーラビリティ}、つまり、ストレージシステムのマシン数を二倍にすればそのシステムのクエリ処理性能も二倍になるというものだ。これを実現するためのポイントは、データを複数マシンにどのように振り分けるかということになる。シャーディングという手法は、読み込みと書き込みを複数のマシンに分散させてストレージシステムをスケールアウトさせるものである。シャーディングは多くのシステムで設計の基本となっている。具体的にはCassandraやHBase、Voldemort、Riak、そして最近ではMongoDBやRedisもそうだ。中には、CouchDBのように単一サーバーでのパフォーマンスを重視してシステムではシャーディング機能を提供しないというプロジェクトもある。しかし、セカンダリプロジェクトがコーディネーターとなって、複数のマシンにそれぞれ独立にインストールした環境に処理を振り分けることもできる。

%% Let's cover a few interchangeable terms you might encounter.  We will
%% use the terms \emph{sharding} and \emph{partitioning} interchangeably.
%% The terms \emph{machine}, \emph{server}, or \emph{node} refer to some
%% physical computer which stores part of the partitioned data.  Finally,
%% a \emph{cluster} or \emph{ring} refers to the set of machines which
%% participate in your storage system.
ここで、いくつかの用語についてまとめておこう。ここでは、\emph{シャーディング}と\emph{パーティショニング}を同じ意味で使う。また、\emph{マシン}や\emph{サーバー}そして\emph{ノード}は、分割されたデータを格納する物理的な計算機を指すものとする。最後に、\emph{クラスタ}あるいは\emph{リング}という用語は、ストレージシステムを構成するマシン群を指すものとする。

%% Sharding means that no one machine has to handle the write workload on
%% the entire dataset, but no one machine can answer queries about the
%% entire dataset.  Most NoSQL systems are key-oriented in both their
%% data and query models, and few queries touch the entire dataset
%% anyway.  Because the primary access method for data in these systems
%% is key-based, sharding is typically key-based as well: some function
%% of the key determines the machine on which a key-value pair is
%% stored.  We'll cover two methods of defining the key-machine mapping:
%% hash partitioning and range partitioning.
シャーディングするということは、どのマシンもそれ単体ではデータセット上のすべての書き込みを処理する必要がなくなるということだ。しかしそれと同時に、どのマシンもそれ単体ではデータセットへのすべての問い合わせには対応しきれないということでもある。多くのNoSQLシステムではキー指向のデータモデルやクエリモデルを採用しているので、いずれにせよデータセット全体にまたがるような問い合わせはほとんどない。これらのシステムではデータにアクセスする主要な方法がキーに基づいているので、シャーディングもまたキーに基づいて行うのがよい。キーに対する何らかの関数が、そのキー・バリューペアをどのマシンに格納するのかを決定する。キーとマシンのマッピング方法を二通り紹介しよう。ハッシュパーティショニングとレンジパーティショニングだ。

%% \begin{aosasect2}{Do Not Shard Until You Have To}
\begin{aosasect2}{必要になるまでシャーディングを避ける}

%% Sharding adds system complexity, and where possible, you should avoid
%% it.  Let's cover two ways to scale without sharding: read replicas and
%% caching.
シャーディングはシステムを複雑化させるものであり、可能な限り避けるべきである。ここでは、シャーディングを使わずにスケールさせる方法を二通り取り上げる。リードレプリカとキャッシュだ。

%% \begin{aosasect3}{Read Replicas}
\begin{aosasect3}{リードレプリカ}

%% Many storage systems see more read requests than write requests.  A
%% simple solution in these cases is to make copies of the data on
%% multiple machines.  All write requests still go to a master node.
%% Read requests go to machines which replicate the data, and are often
%% slightly stale with respect to the data on the write master.
ストレージシステムの多くは、読み込みリクエストのほうが書き込みリクエストより多くなる。そんな場合のシンプルな解決策は、データのコピーを複数のマシン上に置くことだ。書き込みリクエストはすべてマスターノードに任せる。読み込みリクエストはデータのレプリカを持つマシンにまわす。ただしこのレプリカは、書き込みサーバー上のデータよりも若干古いものになることが多い。

%% If you are already replicating your data for multi-server durability
%% in a master-slave configuration, as is common in Redis, CouchDB, or
%% MongoDB, the read slaves can shed some load from the write master.
%% Some queries, such as aggregate summaries of your dataset, which might
%% be expensive and often do not require up-to-the-second freshness, can
%% be executed against the slave replicas.  Generally, the less stringent
%% your demands for freshness of content, the more you can lean on read
%% slaves to improve read-only query performance.
もし既にマスター・スレーブ公正で複数サーバーでのデータの永続化を実現している(RedisやCouchDBそしてMongoDBではそれが一般的)のなら、読み込み用のスレーブが書き込み用のマスターの負荷を多少軽減させることができる。ある種のクエリ、たとえばデータセットのサマリーの集計などは、コストのかかる処理である一方で必ずしも最新のデータを必要とはしないことがある。そんなクエリは、スレーブのレプリカに対して実行すればよい。一般に、データが最新である必要性が少なければ少ないほど、その処理を読み込み用スレーブに任せてクエリのパフォーマンスを稼ぎやすくなる。

\end{aosasect3}

%% \begin{aosasect3}{Caching}
\begin{aosasect3}{キャッシュ}

%% Caching the most popular content in your system often works
%% surprisingly well.  Memcached dedicates blocks of memory on multiple
%% servers to cache data from your data store.  Memcached clients take
%% advantage of several horizontal scalability tricks to distribute load
%% across Memcached installations on different servers.  To add memory to
%% the cache pool, just add another Memcached host.
システム上でよく使われるコンテンツをキャッシュすると、たいていの場合は驚くほどうまく機能する。Memcachedは、複数サーバー上にメモリブロックを確保してデータストアのデータをキャッシュする。Memcachedクライアントは、水平スケーラビリティの技を使って別のサーバー上にあるMemcachedに負荷を分散する。キャッシュプールにメモリを追加するには、単にMemcachedが動くホストを追加するだけでよい。

%% Because Memcached is designed for caching, it does not have as much
%% architectural complexity as the persistent solutions for scaling
%% workloads.  Before considering more complicated solutions, think about
%% whether caching can solve your scalability woes.  Caching is not solely
%% a temporary band-aid: Facebook has Memcached installations in the range
%% of tens of terabytes of memory!
Memcachedはキャッシュ用に設計されているので、処理をスケールさせるための永続化ソリューションのアーキテクチャはそれほど複雑ではない。複雑なソリューションの前に、キャッシュでスケーラビリティの問題を解決できないかどうかを検討してみよう。キャッシュ処理は単なるその場しのぎのバンドエイドではない。FacebookではMemcachedで何と数十テラバイトものメモリを確保しているのだってさ!

\end{aosasect3}

%% Read replicas and caching allow you to scale up your read-heavy
%% workloads.  When you start to increase the frequency of writes and
%% updates to your data, however, you will also increase the load on the
%% master server that contains all of your up-to-date data.  For the rest
%% of this section, we will cover techniques for sharding your write
%% workload across multiple servers.
リードレプリカやキャッシュを使えば、読み込み処理をスケールアップさせることができる。しかし、書き込みやデータ更新の頻度が上がり始めたら、最新状態を保持するマスターサーバーへの負荷が増加することになる。このセクションの後半では、書き込み処理を複数サーバーにシャーディングする方法を扱う。

\end{aosasect2}

%% \begin{aosasect2}{Sharding Through Coordinators}
\begin{aosasect2}{コーディネーターによるシャーディング}

%% The CouchDB project focuses on the single-server experience.  Two
%% projects, Lounge and BigCouch, facilitate sharding CouchDB workloads
%% through an external proxy, which acts as a front end to standalone
%% CouchDB instances.  In this design, the standalone installations are
%% not aware of each other.  The coordinator distributes requests to
%% individual CouchDB instances based on the key of the document being
%% requested.
CouchDBプロジェクトは、単一サーバー上での挙動を重視している。LoungeとBigCouchのふたつのプロジェクトは外部のプロキシを通じてCouchDBへの負荷をシャーディングし、単独のCouchDBインスタンスのフロントエンドとして機能する。この構成では、個々のCouchDBがお互いを意識することがない。コーディネーターが、リクエストされたドキュメントのキーに応じて個々のCoucdDBインスタンスにリクエストを分散させる。

%% Twitter has built the notions of sharding and replication into a
%% coordinating framework called Gizzard\footnote{\url{http://github.com/twitter/gizzard}}.  Gizzard takes standalone data stores of any
%% type---you can build wrappers for SQL or NoSQL storage systems---and
%% arranges them in trees of any depth to partition keys by key range.
%% For fault tolerance, Gizzard can be configured to replicate data to
%% multiple physical machines for the same key range.
Twitterは、シャーディングやレプリケーションの概念をまとめたGizzard\footnote{\url{http://github.com/twitter/gizzard}}というフレームワークを構築した。Gizzardは、任意の型のスタンドアロンデータストア(SQLシステムあるいはNoSQLシステムのラッパーを作れる)を受け取り、キーのレンジでパーティショニングして任意の深さのツリーとしてまとめる。耐障害性を高めるため、Gizzardは同じキーレンジのデータを複数の物理マシンにレプリケートするようにも設定できる。

\end{aosasect2}

%% \begin{aosasect2}{Consistent Hash Rings}
\begin{aosasect2}{コンシステントハッシュリング}

%% Good hash functions distribute a set of keys in a uniform manner.
%% This makes them a powerful tool for distributing key-value pairs
%% among multiple servers.  The academic literature on a technique
%% called \emph{consistent hashing} is extensive, and the first
%% applications of the technique to data stores was in systems called
%% \emph{distributed hash tables} (\emph{DHTs}).  NoSQL systems built
%% around the principles of Amazon's Dynamo adopted this distribution
%% technique, and it appears in Cassandra, Voldemort, and Riak.
よくできたハッシュ関数は、キーのセットを統一された形式で分散させる。これは、キー・バリューのペアを複数のサーバーに分散させるための便利なツールとして使える。学術論文上で\emph{コンシステントハッシュ}と呼ばれる技術は広範囲にわたる。このテクニックをデータストアに応用したはじめての例が\emph{分散ハッシュテーブル}(\emph{DHT: Distributed Hash Tables})というシステムだ。AmazonのDynamoの動作原理を参考にしたNoSQLシステムではこの分散テクニックを採用しており、CassandraやVoldemortそしてRiakなどにそれが見られる。

%% \begin{aosasect3}{Hash Rings by Example}
\begin{aosasect3}{ハッシュリングの実例}

%% \aosafigureTop[150pt]{../images/nosql/hashring.eps}{A Distributed Hash Table Ring}{fig.nosql.hashring}
\aosafigureTop[150pt]{../images/nosql/hashring.eps}{分散ハッシュテーブルリング}{fig.nosql.hashring}

%% Consistent hash rings work as follows.  Say we have a hash function
%% \code{H} that maps keys to uniformly distributed large integer values.  We
%% can form a ring of numbers in the range [1, L] that wraps around
%% itself with these values by taking H(key) mod L for some relatively
%% large integer L\@.  This will map each key into the range [1,L].  A
%% consistent hash ring of servers is formed by taking each server's
%% unique identifier (say its IP address), and applying H to it.  You can
%% get an intuition for how this works by looking at the hash ring formed
%% by five servers (\code{A}-\code{E}) in \aosafigref{fig.nosql.hashring}.
コンシステントハッシュリングは、次のように動作する。まず、ハッシュ関数\code{H}があるとしよう。この関数は、キーを均等に分布する大きな整数値にマップする。比較的大きな整数値Lをとって範囲[1, L]の数のリングを作れば、H(key) mod Lをそのリングに含めることができる。これで、各キーが[1, L]の範囲に収まることになる。サーバーのコンシステントハッシュリングは、各サーバーの固有な識別子(そのIPアドレスなど)にHを適用したものを使って構成される。この動作原理を理解しやすくするために、5台のサーバー(\code{A}-\code{E})からなるハッシュリングの例を\aosafigref{fig.nosql.hashring}に示す。

%% There, we picked \code{L = 1000}.  Let's say that \code{H(A) mod
%% L = 7}, \code{H(B) mod L = 234}, \code{H(C) mod L = 447}, \code{H(D)
%% mod L = 660}, and \code{H(E) mod L = 875}.  We can now tell which
%% server a key should live on.  To do this, we map all keys to a server
%% by seeing if it falls in the range between that server and the next
%% one in the ring.  For example, \code{A} is responsible for keys whose
%% hash value falls in the range [7,233], and \code{E} is responsible for
%% keys in the range [875, 6] (this range wraps around on itself at
%% 1000).  So if \code{H('employee30') mod L = 899}, it will be stored by
%% server \code{E}, and if \code{H('employee31') mod L = 234}, it will be
%% stored on server \code{B}.
ここでは、\code{L = 1000}とした。\code{H(A) mod L = 7}、\code{H(B) mod L = 234}、\code{H(C) mod L = 447}、\code{H(D) mod L = 660}、そして\code{H(E) mod L = 875}であるとしよう。これで、キーがどのサーバーに配置されるかがわかるようになった。リング内で、あるサーバーとその次のサーバーの間にキーが収まる場合に、そのサーバーにキーを格納することになる。たとえば、\code{A}が受け持つキーはそのハッシュが[7, 233]の範囲になるものであり、\code{E}が受け持つキーはそのハッシュが[875, 6]の範囲(これは、値が1000の部分をまたがっている)になるものである。つまり、もし\code{H('employee30') mod L = 899}になるのならこのデータはサーバー\code{E}に格納されるし、\code{H('employee31') mod L = 234}になるとしたらこのデータはサーバー\code{B}に格納される。

\end{aosasect3}

%% \begin{aosasect3}{Replicating Data}
\begin{aosasect3}{データのレプリケーション}

%% Replication for multi-server durability is achieved by passing the
%% keys and values in one server's assigned range to the servers
%% following it in the ring.  For example, with a replication factor of
%% 3, keys mapped to the range [7,233] will be stored on servers
%% \code{A}, \code{B}, and \code{C}.  If \code{A} were to fail, its
%% neighbors \code{B} and \code{C} would take over its workload.  In some designs,
%% \code{E} would replicate and take over \code{A}'s workload temporarily, 
%% since its range would expand to include \code{A}'s.
複数サーバーでの永続化のためにレプリケーションをするには、あるサーバーの担当範囲に割り当てられたキーと値のペアをリング内でのその次のサーバーに渡せばよい。たとえば、三重のレプリケーションを行うには、範囲[7,233]にマップされたキーをサーバー\code{A}、\code{B}、そして\code{C}に格納する。仮に\code{A}がダウンしたら、隣にある\code{B}と\code{C}がその範囲を受け持つ。設計によっては、\code{E}にレプリケートして\code{A}の担当分を一時的に受け持つこともある。この場合は担当範囲を拡張して\code{A}の範囲も含めるようにする。

\end{aosasect3}

%% \begin{aosasect3}{Achieving Better Distribution}
\begin{aosasect3}{よりよい振り分け}

%% While hashing is statistically effective at uniformly distributing a
%% keyspace, it usually requires many servers before it distributes
%% evenly.  Unfortunately, we often start with a small number of servers
%% that are not perfectly spaced apart from one-another by the hash
%% function.  In our example, \code{A}'s key range is of length 227,
%% whereas \code{E}'s range is 132.  This leads to uneven load on
%% different servers.  It also makes it difficult for servers to take
%% over for one-another when they fail, since a neighbor suddenly has to
%% take control of the entire range of the failed server.
ハッシュはキー空間を均等分布させるという点では統計的に有効であるが、均等に分布させるには通常はある程度多くのサーバーを必要とする。残念ながら、たいていは少数のサーバーからスタートすることが多い。そしてその段階では、ハッシュ関数がうまくキーを分散させてはくれない。先ほどの例で見ると、\code{A}の担当範囲の長さは227であるのに対して\code{E}の担当範囲は132しかない。こんな状態だと、サーバーによって負荷が違うということになるだろう。また、どれかひとつのサーバーがダウンしたときに代わりを受け持つのも難しくなる。隣のサーバーが、ダウンしたサーバーの担当範囲全体を制御しなければならなくなるからである。

%% To solve the problem of uneven large key ranges, many DHTs including
%% Riak create several `virtual' nodes per physical machine.  For
%% example, with 4 virtual nodes, server \code{A} will act as server
%% \code{A\_1}, \code{A\_2}, \code{A\_3}, and \code{A\_4}.  Each virtual
%% node hashes to a different value, giving it more opportunity to manage
%% keys distributed to different parts of the keyspace.  Voldemort takes
%% a similar approach, in which the number of partitions is manually
%% configured and usually larger than the number of servers, resulting in
%% each server receiving a number of smaller partitions.
担当するキーの範囲にばらつきが出てしまう問題を解決するために、Riakを含む多くのDHTは、物理マシン単位でいくつか`仮想'ノードを作成する。たとえば、4つの仮想ノードを作ったサーバー\code{A}が、サーバー\code{A\_1}、\code{A\_2}、\code{A\_3}、そして\code{A\_4}として動作するといった具合だ。各仮想ノードには異なるハッシュ値が割り当てられ、キー空間の各部分によりうまく分散させられるようにする。Voldemortも同様の手法を採用しており、パーティションの数を手動で設定できるようになっている。通常はサーバーの数よりパーティションの数を多くするので、結果的に各サーバーが複数のパーティションを受け持つことになる。

%% Cassandra does not assign multiple small partitions to each server,
%% resulting in sometimes uneven key range distributions.  For
%% load-balancing, Cassandra has an asynchronous process which adjusts
%% the location of servers on the ring depending on their historic load.
Cassandraは、各サーバーで複数の小さなパーティションを担当するということはしない。そのため、時にはキーの範囲の分散が均一にならないこともある。ロードバランス用として、Cassandraには非同期プロセスが用意されている。このプロセスは、これまでの負荷の履歴に基づいてリング上でのサーバーの配置を調整する。

\end{aosasect3}

\end{aosasect2}

\vspace{-0.2cm} % remove some space to rescue orphan from next page
%% \begin{aosasect2}{Range Partitioning}
\begin{aosasect2}{レンジパーティショニング}
\vspace{-0.1cm} % remove some space to rescue orphan from next page

%% In the range partitioning approach to sharding, some machines in your
%% system keep metadata about which servers contain which key ranges.
%% This metadata is consulted to route key and range lookups to the
%% appropriate servers.  Like the consistent hash ring approach, this
%% range partitioning splits the keyspace into ranges, with each key
%% range being managed by one machine and potentially replicated to
%% others.  Unlike the consistent hashing approach, two keys that are
%% next to each other in the key's sort order are likely to appear in the
%% same partition.  This reduces the size of the routing metadata, as
%% large ranges are compressed to [start, end] markers.
レンジパーティショニング方式によるシャーディングでは、システム内の何台かのマシンが「どのサーバーがどのキー範囲を受け持つか」というメタ情報を保持する。このメタ情報への問い合わせによって、キー範囲の検索と適切なサーバーへの振り分けを行う。コンシステントハッシュリングの手法と同様、レンジパーティショニングもキー空間をいくつかの範囲に分割する。そして各範囲をひとつのマシンが管理し、場合によっては他のマシンにレプリケートしたりする。コンシステントハッシュ方式と違うところは、キーのソート順で隣同士になるキーがほぼ同じパーティションに収まるという点だ。これにより、ルーティング用のメタデータのサイズを軽減できる。範囲を表すには単に[開始位置, 終了位置]の印があればよいだけだからである。

%% In adding active record-keeping of the \emph{range-to-server} mapping,
%% the range partitioning approach allows for more fine-grained control
%% of load-shedding from heavily loaded servers.  If a specific key range
%% sees higher traffic than other ranges, a load manager can reduce the
%% size of the range on that server, or reduce the number of shards that
%% this server serves.  The added freedom to actively manage load comes
%% at the expense of extra architectural components which monitor and
%% route shards.
\emph{キー範囲とサーバー}のマッピング情報を更新し続ける際に、レンジパーティショニング方式では高負荷なサーバーの負荷分散をよりきめ細やかに制御できるようになる。特定のキー範囲が他の範囲に比べてトラフィックが多くなるようなら、ロードマネージャーはそのサーバーが担当する範囲を狭めることもできるし、そのサーバーが担当するシャードの数を減らすこともできる。動的に負荷を調整できるという新たな自由を得るために使ったのは、シャードを監視したりルーティングしたりするための追加コンポーネントだ。

\vspace{-0.1cm} % remove some space to rescue orphan from next page
%% \begin{aosasect3}{The BigTable Way}
\begin{aosasect3}{BigTableの手法}

%% Google's BigTable paper describes a range-partitioning hierarchical
%% technique for sharding data into tablets.  A tablet stores a range of
%% row keys and values within a column family.  It maintains all
%% of the necessary logs and data structures to answer queries about the
%% keys in its assigned range.  Tablet servers serve multiple tablets
%% depending on the load each tablet is experiencing.
GoogleによるBigTableに関する論文には、階層化レンジパーティショニングでデータをタブレットにシャーディングする手法が解説されている。一つのタブレットが、一定範囲の行のキーとカラムファミリー内の値を保持する。タブレットは必要なログをすべて保持し、自分が担当する範囲のキーに関する問い合わせに答えるためのデータ構造もすべて保持する。タブレットサーバーは、各タブレットにかかる負荷に応じて複数のタブレットを担当する。

%% Each tablet is kept at a size of 100-200 MB\@.  As tablets change in size, two 
%% small tablets with adjoining key ranges might be combined, or a large tablet might be
%% split in two.  A master server analyzes tablet size,
%% load, and tablet server availability.  The master adjusts which tablet
%% server serves which tablets at any time.
各タブレットは、100から200MBのサイズを保つ。タブレットのサイズが変われば、隣り合うキー範囲の二つの小さなタブレットを一つにまとめたり、あるいは大きなタブレットを二つに分割したりする。マスターサーバーが、タブレットのサイズや負荷そしてタブレットサーバーの稼働状態を解析する。そして、マスターサーバーは、どのタブレットサーバーがどのタブレットを担当するのかを常時調節する。

%% \aosafigure[300pt]{../images/nosql/bigtable.eps}{BigTable-based Range Partitioning}{fig.nosql.bigtable}
\aosafigure[300pt]{../images/nosql/bigtable.eps}{BigTableベースのレンジパーティショニング}{fig.nosql.bigtable}

%% The master server maintains the tablet assignment in a metadata table.
%% Because this metadata can get large, the metadata table is also
%% sharded into tablets that map key ranges to tablets and tablet servers
%% responsible for those ranges.  This results in a three-layer hierarchy
%% traversal for clients to find a key on its hosting tablet server,
%% as depicted in \aosafigref{fig.nosql.bigtable}.
マスターサーバーは、タブレットの割り当てをメタデータテーブルで管理する。このメタデータはかなり大きくなる可能性があるので、メタデータテーブル自体も複数のタブレットにシャーディングしてキー範囲とタブレットを関連づける。タブレットサーバーが、この範囲の管理を行う。その結果、クライアントは三階層の走査を経てキーの保存先のタブレットサーバーを知ることになる。その様子を\aosafigref{fig.nosql.bigtable}に示す。

%% Let's look at an example.  A client searching for key
%% \code{900} will query server \code{A}, which stores the tablet for
%% metadata level 0.  This tablet identifies the metadata level 1 tablet
%% on server 6 containing key ranges 500-1500.  The client sends a
%% request to server \code{B} with this key, which responds that the
%% tablet containing keys 850-950 is found on a tablet on server
%% C\@.  Finally, the client sends the key request to server \code{C}, and
%% gets the row data back for its query.  Metadata tablets at level 0 and
%% 1 may be cached by the client, which avoids putting undue load on
%% their tablet servers from repeat queries.  The BigTable paper explains
%% that this 3-level hierarchy can accommodate $2^{61}$ bytes worth of storage
%% using 128MB tablets.
実際の例を見てみよう。クライアントがキー\code{900}を検索しようとすると、サーバー\code{A}に問い合わせを行う。このサーバーには、レベル0のメタデータ用のタブレットが格納されている。このタブレットを見れば、レベル1のメタデータあがサーバー6上のタブレットにあることがわかる。このタブレットには500-1500の範囲のキーが含まれる。クライアントはサーバー\code{B}に対してこのキーでリクエストを送る。そして、キー850-950を含むタブレットがサーバーC上にあるという応答を得る。最終的に、クライアントはそのキーについてのリクエストをサーバー\code{C}に送り、問い合わせ結果の行を取得する。レベル0とレベル1のメタデータタブレットはクライアント側でキャッシュしてもかまわない。そうすれば、タブレットサーバーに対する同じような問い合わせの繰り返しを回避できる。BigTableの論文では、この三段階の階層によって$2^{61}$バイトのストレージを128MBのタブレットで対応できるとしている。

\end{aosasect3}

\vspace{-0.1cm} % remove some space to rescue orphan from next page
%% \begin{aosasect3}{Handling Failures}
\begin{aosasect3}{障害の処理}

%% The master is a single point of failure in the BigTable design, but
%% can go down temporarily without affecting requests to tablet servers.
%% If a tablet server fails while serving tablet requests, it is up to
%% the master to recognize this and re-assign its tablets while requests
%% temporarily fail.
BigTableの設計では、マスターが単一障害点になる。しかし、タブレットサーバーへのリクエストに影響が及ばないように一時的にダウンさせることも可能だ。タブレットへのリクエストを処理するタブレットサーバーがダウンすれば、マスターがそれを認識してそのタブレットの担当を切り替えるまではリクエストが一時的に失敗するようになる。

%% In order to recognize and handle machine failures, the BigTable paper
%% describes the use of Chubby, a distributed locking system for managing
%% server membership and liveness.
%% ZooKeeper\footnote{\url{http://hadoop.apache.org/zookeeper/}} is the
%% open source implementation of Chubby, and several Hadoop-based
%% projects utilize it to manage secondary master servers and tablet
%% server reassignment.
マシンの障害を認識して対応するための方法として、BigTableの論文ではChubbyを使っている。これは分散ロックシステムで、サーバーの死活監視を行うものである。ZooKeeper\footnote{\url{http://hadoop.apache.org/zookeeper/}}はChubbyのオープンソース実装で、Hadoopベースのプロジェクトの中には、これを使ってセカンダリマスターサーバーやタブレットサーバーの再配置を行うものもある。

\end{aosasect3}

%% \begin{aosasect3}{Range Partitioning-based NoSQL Projects}
\begin{aosasect3}{レンジパーティショニングベースのNoSQLプロジェクト}

%% HBase employs BigTable's hierarchical approach to range-partitioning.
%% Underlying tablet data is stored in Hadoop's distributed filesystem
%% (HDFS).  HDFS handles data replication and consistency among replicas,
%% leaving tablet servers to handle requests, update storage structures,
%% and initiate tablet splits and compactions.
HBaseは、BigTableの階層方式を使ってレンジパーティショニングを行う。ベースとなるタブレットのデータはHadoopの分散ファイルシステム(HDFS)に格納する。HDFSがデータのレプリケーションやレプリカ間の整合性を管理する。そして、タブレットサーバー側ではリクエストの処理やストレージの更新、タブレットの分割や統合を管理する。

%% MongoDB handles range partitioning in a manner similar to that of
%% BigTable.  Several configuration nodes store and manage the routing
%% tables that specify which storage node is responsible for which key
%% ranges.  These configuration nodes stay in sync through a protocol
%% called \emph{two-phase commit}, and serve as a hybrid of BigTable's
%% master for specifying ranges and Chubby for highly available
%% configuration management.  Separate routing processes, which are
%% stateless, keep track of the most recent routing configuration and
%% route key requests to the appropriate storage nodes.  Storage nodes
%% are arranged in replica sets to handle replication.
MongoDBも、BigTableと同様の方法でレンジパーティショニングを処理する。いくつかの設定ノードがルーティングテーブルを管理して、このルーティングテーブルを使ってどのストレージノードがどの範囲のキーを担当するかを決定する。設定ノード間の同期は\emph{二相コミット}というプロトコルで行い、BigTableのマスターが受け持つ範囲指定機能とChubbyが受け持つ高可用性のための構成管理機能の両方を提供する。ステートレスで動くルーティングプロセスとは別に、直近のルーティング設定を追跡し続けることでキーへのリクエストを適切なストレージノードに振り分ける。ストレージノードはレプリカセット内に置かれ、レプリカセットでレプリケーションを行う。

%% Cassandra provides an order-preserving partitioner if you wish to
%% allow fast range scans over your data.  Cassandra nodes are still arranged
%% in a ring using consistent hashing, but rather than hashing a
%% key-value pair onto the ring to determine the server to which it
%% should be assigned, the key is simply mapped onto the server which
%% controls the range in which the key naturally fits.  For example, keys
%% 20 and 21 would both be mapped to server A in our consistent hash ring
%% in \aosafigref{fig.nosql.hashring}, rather than being hashed and
%% randomly distributed in the ring.
Cassandraでは順序を保持したパーティショニング機能を提供しており、データに対するレンジスキャンを高速に行いたい場合に利用できる。Cassandraのノードもコンシステントハッシュを使ってリング内に配置される。しかし、キー・バリューのペアをハッシュして割り当て先のサーバーを決めるのではなく、キーそのものを単純にサーバーにマップする。そうすることで、キーが必然的にフィットする範囲を制御できるようになる。たとえばキー20と21は、\aosafigref{fig.nosql.hashring}のコンシステントハッシュリング上でどちらもサーバーAにマップされる。ハッシュしてリング内でランダムに分散させるわけではない。

%% Twitter's Gizzard framework for managing partitioned and replicated
%% data across many back ends uses range partitioning to shard data.
%% Routing servers form hierarchies of any depth, assigning ranges of
%% keys to servers below them in the hierarchy.  These servers either
%% store data for keys in their assigned range, or route to yet another
%% layer of routing servers.  Replication in this model is achieved by sending
%% updates to multiple machines for a key range.  Gizzard routing nodes
%% manage failed writes in different manner than other NoSQL systems.
%% Gizzard requires that system designers make all updates idempotent
%% (they can be run twice).  When a storage node fails, routing nodes
%% cache and repeatedly send updates to the node until the update is
%% confirmed.
TwitterのGizzardフレームワークは、分割され、レプリケートされたデータをさまざまなバックエンドにまたがって管理するもので、レンジパーティショニングを使ってデータをシャーディングする。ルーティングサーバーは任意のレベルの階層構造を構成し、キー範囲をその階層下のサーバーに割り当てる。各サーバーは自分に割り当てられたキー範囲のデータを格納したり、別の層のルーティングサーバーに処理を振ったりする。このモデルにおけるレプリケーションは、あるキー範囲の更新を複数のマシンに送信することで実現する。Gizzardのルーティングノードは、書き込みに失敗したときの対応方法が他のNoSQLシステムとは異なる。Gizzardを使ったシステムでは、すべての更新が冪等(何度実行しても結果が変わらない)でなければならない。ストレージノードがダウンしているときは、ルーティングノードがその処理をキャッシュし、更新が確認できるまで何度もその処理を送信し続ける。

\end{aosasect3}

\end{aosasect2}

%% \begin{aosasect2}{Which Partitioning Scheme to Use}
\begin{aosasect2}{どのパーティショニング方式を採用するか}

%% Given the hash- and range-based approaches to sharding, which is
%% preferable?  It depends.  Range partitioning is the obvious choice to
%% use when you will frequently be performing range scans over the keys
%% of your data.  As you read values in order by key, you will not jump
%% to random nodes in the network, which would incur heavy network
%% overhead.  But if you do not require range scans, which sharding
%% scheme should you use?
ハッシュ方式とレンジ方式、シャーディングの手法としてどちらが適切なのかって? それは状況による。明らかにレンジパーティショニングを選ぶべきなのは、たとえばキーによる検索よりも範囲指定による検索が多発するような場面だ。キーの順に値を読み込むことになるので、そうしておけばネットワーク上のあちこちのノードを飛び回る必要がなくなる。ノードを移るときのネットワークのオーバーヘッドは馬鹿にできない。しかし、範囲指定の検索が不要な場合には、どちらの方式を選べばよいのだろう?

%% Hash partitioning gives reasonable distribution of data across nodes,
%% and random skew can be reduced with virtual nodes.  Routing is simple
%% in the hash partitioning scheme: for the most part, the hash function
%% can be executed by clients to find the appropriate server.  With more
%% complicated rebalancing schemes, finding the right node for a key
%% becomes more difficult.
ハッシュパーティショニングを使えば、データを複数のノードに適切に分散させることができる。そして、データの非対称性も仮想ノードで軽減できる。ハッシュパーティショニング方式では、ルーティングもシンプルになる。ほとんどの場合は、クライアント側でハッシュ関数を実行すれば問い合わせ先のサーバーを確定できる。バランスを調整するための仕組みを導入している場合は、あるキーに対して適切なノードを見つけるのは少し難しくなる。

%% Range partitioning requires the upfront cost of maintaining
%% routing and configuration nodes, which can see heavy load and become
%% central points of failure in the absence of relatively complex fault
%% tolerance schemes.  Done well, however, range-partitioned data can be
%% load-balanced in small chunks which can be reassigned in high-load
%% situations.  If a server goes down, its assigned ranges can be
%% distributed to many servers, rather than loading the server's
%% immediate neighbors during downtime.
レンジパーティショニングは、ノードのルーティングや構成を管理するための事前コストが必要となる。この処理の負荷は高くなりがちで、耐障害性をきちんと考慮していないと障害の主因になるだろう。しかし、うまくやれば、レンジパーティショニングで分割したデータは小さいチャンクで負荷分散できるようになり、負荷が高くなったときの調整も可能となる。かりにひとつのサーバーがダウンしたとしても、そこに割り当てられていた範囲を多数のサーバーに分散させることができ、ダウンしたサーバーの直近のサーバーだけに負荷をかけることはない。

\end{aosasect2}

\end{aosasect1}

%% \begin{aosasect1}{Consistency}
\begin{aosasect1}{整合性}
\label{sec.nosql.consistency}

%% Having spoken about the virtues of replicating data to multiple
%% machines for durability and spreading load, it's time to let you in on
%% a secret: keeping replicas of your data on multiple machines
%% consistent with one-another is hard.  In practice, replicas will crash
%% and get out of sync, replicas will crash and never come back, networks
%% will partition two sets of replicas, and messages between machines
%% will get delayed or lost.  There are two major approaches to data
%% consistency in the NoSQL ecosystem.  The first is strong consistency, where all
%% replicas remain in sync.  The second is eventual consistency, where replicas are
%% allowed to get out of sync, but eventually catch up with one-another.
%% Let's first get into why the second option is an appropriate
%% consideration by understanding a fundamental property of distributed
%% computing.  After that, we'll jump into the details of each approach.
これまでは、「データを複数マシンにレプリケートすれば永続化できるし負荷分散もできる」と、その利点だけを説明してきた。このあたりでその実態も書いておこう。複数マシンにデータのレプリカを置いてお互いの整合性を保つというのは、大変な作業だ。実際のところ、レプリカが壊れて同期できなくなることもあるだろうし壊れたデータを復旧できなくなることもあるだろう。ネットワーク上で複数のレプリカセットができてしまったり、マシン間のメッセージが遅延したり途中で消えてしまったりといったこともあり得る。NoSQLの世界でデータの整合性を保つための方法としてよく使われるのは、次の二通りの手法だ。ひとつは強整合性(strong consistency)で、これはすべてのレプリカを同期させる。もうひとつが結果整合性(eventual consistency)で、こちらの方式ではレプリカが同期されていなくてもかまわないが、最終的にはお互い相手側の状態に追いつけるようにしておかなければならない。まず最初に、どんな場合に結果整合性が選択肢に入るのかを分散コンピューティングの本質から考える。その後で、それぞれの手法の詳細を見ていこう。

%% \begin{aosasect2}{A Little Bit About CAP}
\begin{aosasect2}{CAPについて}

%% Why are we considering anything short of strong consistency guarantees
%% over our data?  It all comes down to a property of distributed systems
%% architected for modern networking equipment.  The idea was first
%% proposed by Eric Brewer as the \emph{CAP Theorem}, and later proved by
%% Gilbert and Lynch~\cite{bib:captheorem}.  The theorem first presents three
%% properties of distributed systems which make up the acronym CAP:
データに対する強整合性を保証できなくなることについて、なぜそんなに考慮するのだろう? すべては、今どきのネットワーク機器上で構築された分散システムの特性によるものだ。Eric Brewerが初めて提唱した\emph{CAP定理}は、後にGilbertとLynch~\cite{bib:captheorem}によって証明された。この定理では、まず最初に分散システムの三つの特性を提示する。この頭文字をまとめた頭字語がCAPである。

\begin{aosadescription}

  %% \item{Consistency}: do all replicas of a piece of data always
  %% logically agree on the same version of that data by the time you
  %% read it?  (This concept of consistency is different than the C in ACID.)
  \item{整合性(Consistency)}: あるデータのすべてのレプリカについて、どれを読んでも同じバージョンのデータを得られるか?(ここでいう整合性は、ACIDのCとは異なる)

  %% \item{Availability}: Do replicas respond to read and write requests regardless
  %% of how many replicas are inaccessible?
  \item{可用性(Availability)}: アクセス不能なレプリカがいくつあっても、読み書きのリクエストに対応できるか?

  %% \item{Partition tolerance}: Can the system continue to operate
  %% even if some replicas temporarily lose the ability to communicate
  %% with each other over the network?
  \item{耐分断性(Partition tolerance)}: レプリカの一部が一時的にネットワーク上で他と分断されたときに、それでもシステムを稼働させ続けられるか?

\end{aosadescription}

%% The theorem then goes on to say that a storage system which operates on
%% multiple computers can only achieve two of these properties at the
%% expense of a third.  Also, we are forced to implement partition-tolerant
%% systems.  On current networking
%% hardware using current messaging protocols, packets can be lost,
%% switches can fail, and there is no way to know whether the network is
%% down or the server you are trying to send a message to is unavailable.
%% All NoSQL systems should be partition-tolerant.  The remaining choice
%% is between consistency and availability.  No NoSQL system can provide
%% both at the same time.
そして、定理はさらにこう続く。複数台のコンピュータで構成されるストレージシステムは、この三つのうちの二つまでしか達成できず、その二つを達成するためには残りの一つが犠牲になってしまうのだ、と。また我々は、耐分断性を保証するシステムを実装せざるを得ない。現状のネットワーク機器やメッセージングプロトコルでは、パケットをロストすることもあればスイッチが故障することもある。そして、ネットワークがダウンしていたりメッセージの送信先のサーバーが存在しなかったりといったことを知るすべもない。すべてのNoSQLシステムで、耐分断性が必須となる。残された選択肢は、整合性と可用性のどちらを妥協するかである。両方を保証できるようなNoSQLシステムは存在しない。

%% Opting for consistency means that your replicated data will not be out
%% of sync across replicas.  An easy way to achieve consistency is to
%% require that all replicas acknowledge updates.  If a replica goes down
%% and you can not confirm data updates on it, then you degrade
%% availability on its keys.  This means that until all replicas recover and respond, the user can not
%% receive successful acknowledgment of their update operation.  Thus, opting
%% for consistency is opting for a lack of round-the-clock availability
%% for each data item.
整合性を保証するというのは、レプリカ間でのデータの同期をきちんと保つということだ。これを実現する簡単な方法は、すべてのレプリカに対する更新を確認することである。もしどれか一つのレプリカがダウンして更新確認を受け取れなかった場合は、そのキーの可用性を下げる。つまり、ダウンしたレプリカが復旧して確認の応答を返すまでは、その更新処理が成功したとは見なさないということだ。つまり、整合性を保証しようとすると、各データアイテムに対する24時間体制の可用性は保証できなくなる。

%% Opting for availability means that when a user issues an operation,
%% replicas should act on the
%% data they have, regardless of the state of other replicas.  This may
%% lead to diverging consistency of data across replicas, since they
%% weren't required to acknowledge all updates, and some replicas may
%% have not noted all updates.
可用性を保証するというのは、ユーザーが何らかの操作を実行したときには、他のレプリカの状態がどうであるかにかかわらず自身が持つデータ上で操作を受け付けなければならないということだ。これは、レプリカ間でのデータの整合性を失ってしまうことにつながる。というのも、各レプリカにすべての更新が行き渡っているかどうかの確認がないので、中には一部の更新を受け取れていないレプリカも発生しうるからである。

%% The implications of the CAP theorem lead to the strong consistency and
%% eventual consistency approaches to building NoSQL data stores.  Other
%% approaches exist, such as the relaxed consistency and relaxed
%% availability approach presented in Yahoo!'s PNUTS~\cite{bib:pnuts} system.  None of
%% the open source NoSQL systems we discuss has adopted this technique yet,
%% so we will not discuss it further.
CAP定理からの帰結として、強整合性あるいは結果整合性のいずれかの手法でNoSQLデータストアが作られることになった。それ以外の手法も存在して、たとえばYahoo!のPNUTS~\cite{bib:pnuts}システムでは、緩い整合性と緩い可用性(relaxed consistency and relaxed availability)という手法をとっている。しかし、本章で扱っているオープンソースのNoSQLシステムの中にはまだこの手法を採用しているものが存在しないので、本章ではこの手法は扱わない。

\end{aosasect2}

%% \begin{aosasect2}{Strong Consistency}
\begin{aosasect2}{強整合性}

%% Systems which promote strong consistency ensure that the replicas of a
%% data item will always be able to come to consensus on the value of a
%% key.  Some replicas may be out of sync with one-another, but when the
%% user asks for the value of \code{employee30:salary}, the machines have
%% a way to consistently agree on the value the user sees.  How this
%% works is best explained with numbers.
強整合性を謳うシステムが保証するのは、データ項目のレプリカが常にそのキーの値を保持しているということだ。レプリカの中には、他のレプリカとの同期がとれなくなっているものもあるかもしれない。しかしそんな場合であっても、たとえばユーザーが\code{employee30:salary}の値を問い合わせれば、ユーザーに返す値は常に一貫性のあるものとなる。その原理を、数字で説明しよう。

%% Say we replicate a key on N machines.  Some machine, perhaps one of
%% the \code{N}, serves as a coordinator for each user request.  The
%% coordinator ensures that a certain number of the \code{N} machines has
%% received and acknowledged each request.  When a write or update occurs
%% to a key, the coordinator does not confirm with the user that the
%% write occurred until \code{W} replicas confirm that they have received
%% the update.  When a user wants to read the value for some key, the
%% coordinator responds when at least R have responded with the same
%% value.  We say that the system exemplifies strong consistency if
%% \code{ R+W{\textgreater}N}.
ひとつのキーをN台のマシンにレプリケートしたものとする。あるマシン、おそらく\code{N}台のなかのどれかが、コーディネーターとしてユーザーからのリクエストを処理する。このコーディネーターは、\code{N}台のマシンのうちの一定台数以上が各リクエストを受け付けたことを保証する。あるキーに対する書き込みや更新があれば、少なくとも\code{W}台のマシンがその更新を処理し終えたことを確認するまでコーディネーターはユーザーに応答を返さない。ユーザーが何らかのキーの値を読もうとしたときには、少なくともR台から同じ値を受け取るまでコーディネーターは応答を返さない。このとき、\code{ R+W{\textgreater}N}であればシステムの強整合性を実証できるものとする。

%% Putting some numbers to this idea, let's say that we're replicating
%% each key across N=3 machines (call them \code{A}, \code{B}, and
%% \code{C}).  Say that the key \code{employee30:salary} is initially set
%% to the value \$20,000, but we want to give \code{employee30} a raise
%% to \$30,000.  Let's require that at least \code{W=2} of \code{A},
%% \code{B}, or \code{C} acknowledge each write request for a key.  When
%% \code{A} and \code{B} confirm the write request for \code{(employee30:salary,
%%   \$30,000)}, the coordinator lets the user know that
%% \code{employee30:salary} is safely updated.  Let's assume that machine
%% C never received the write request for \code{employee30:salary}, so it
%% still has the value \$20,000.  When a coordinator gets a read request
%% for key \code{employee30:salary}, it will send that request to all 3
%% machines:
この考え方を、実際に数字を入れて確認しよう。各キーをN=3でレプリケートする(それぞれ\code{A}、\code{B}、\code{C}とする)。キー\code{employee30:salary}の初期値は\$20,000だったが、ここで\code{employee30}を\$30,000に昇給させることになった。要件として、\code{W=2}つまり\code{A}、\code{B}、\code{C}のうちで少なくとも2台が書き込みリクエストを受け付けることとする。このとき\code{A}と\code{B}が書き込みリクエスト\code{(employee30:salary, \$30,000)}を受け付けると、コーディネーターはユーザーに対して\code{employee30:salary}が更新できたと伝える。マシンCが仮に\code{employee30:salary}へのリクエストを受け取れなかったとしよう。つまり、マシンCの値は\$20,000のままである。ここでコーディネーターがキー\code{employee30:salary}に対する読み込みリクエストを受け取ると、そのリクエストを3台のマシンすべてに送信する。

\begin{aosaitemize}

  %% \item If we set \code{R=1}, and machine \code{C} responds first with
  %% \$20,000, our employee will not be very happy.
  \item もし仮に\code{R=1}で最初に応答したのが\code{C}だったとしたら、結果は\$20,000となってこの社員はあまりうれしくないだろう。

  %% \item However, if we set \code{R=2}, the coordinator will see the
  %% value from \code{C}, wait for a second response from \code{A} or
  %% \code{B}, which will conflict with \code{C}'s outdated value, and
  %% finally receive a response from the third machine, which will
  %% confirm that \$30,000 is the majority opinion.
  \item しかし、もし\code{R=2}にしておけばコーディネーターは最初に\code{C}の値を受け取っても\code{A}あるいは\code{B}からの二番目の応答を待ち続ける。どちらが先に来ても先ほどの\code{C}の値と食い違っているのでさらに待ち続け、最終的に三番目のマシンからの応答を受け取った時点で\$30,000が多数派であることを確認できる。

\end{aosaitemize}

%% So in order to achieve strong consistency in this case, we need to set
%% \code{R>=2} so that \code{R+W>3}.
したがって、この場合に強整合性を満たすには、\code{R>=2}にして\code{R+W>3}を満たす必要がある。

%% What happens when \code{W} replicas do not respond to a write request,
%% or \code{R} replicas do not respond to a read request with a
%% consistent response?  The coordinator can timeout eventually and send
%% the user an error, or wait until the situation corrects itself.
%% Either way, the system is considered unavailable for that request for
%% at least some time.
書き込みリクエストで\code{W}台のレプリカから応答が返ってこなかったり、読み込みリクエストで一貫性のある結果が\code{R}台以上のレプリカから得られなかったりした場合には何が起こるのだろう?コーディネーター側としては、最終的にタイムアウトを発生させてユーザーにエラーを返すこともできるし、要件を満たすまでずっと待ち続けることもできる。どちらにしても、そのリクエストについては少なくとも一定期間はアクセス不能とみなされる。

%% Your choice of \code{R} and \code{W} affect how many machines can act
%% strangely before your system becomes unavailable for different actions
%% on a key.  If you force all of your replicas to acknowledge writes,
%% for example, then \code{W=N}, and write operations will hang or fail
%% on any replica failure.  A common choice is \code{R + W = N + 1},
%% the minimum required for strong consistency while still allowing for
%% temporary disagreement between replicas.  Many strong consistency
%% systems opt for \code{W=N} and \code{R=1}, since they then do not have
%% to design for nodes going out of sync.
\code{R}と\code{W}をどのように設定するかによって、何台のマシンが不調になってもキーに対するさまざまな操作が可能になるかが決まる。たとえば書き込み操作はすべてのレプリカにきちんと反映させたいのなら、\code{W=N}とすることになる。この場合、どれか一台でもレプリカが応答しなければ、書き込みはハングしたり失敗したりする。よくある選択肢は\code{R + W = N + 1}とするもので、こうすれば強整合性を維持するために最低限必要な稼働台数を最小に抑えられる。多くの強整合性システムは\code{W=N}そして\code{R=1}という設定を選んでいる。そうすれば、同期に失敗したノードをどうするかを考えずに済むからである。

%% HBase bases its replicated storage on HDFS, a distributed storage layer.  HDFS provides strong consistency
%% guarantees.  In HDFS, a write cannot succeed until it has been
%% replicated to all \code{N} (usually 2 or 3) replicas, so \code{W = N}.
%% A read will be satisfied by a single replica, so \code{R = 1}.  To
%% avoid bogging down write-intensive workloads, data is transferred from
%% the user to the replicas asynchronously in parallel.  Once all
%% replicas acknowledge that they have received copies of the data, the
%% final step of swapping the new data in to the system is performed
%% atomically and consistently across all replicas.
HBaseはHDFS上でストレージをレプリケートする。これは分散型のストレージ層だ。HDFSは強整合性を保証する。HDFSでは、全\code{N}台(通常は2あるいは3)のレプリカに書き込み終えるまで書き込みは成功しない。つまり\code{W = N}である。読み込みはひとつのレプリカだけで応答できるので、\code{R = 1}となる。大量の書き込みによるダウンを避けるため、ユーザーから各レプリカへのデータの転送は、非同期で並列処理される。すべてのレプリカがデータのコピーを受け取ったら、最後にシステム上のデータを新しいものに置き換える処理が行われる。これはアトミックな処理で、全レプリカの整合性を保ったものだ。

\end{aosasect2}

%% \begin{aosasect2}{Eventual Consistency}
\begin{aosasect2}{結果整合性}

%% Dynamo-based systems, which include Voldemort, Cassandra, and Riak,
%% allow the user to specify \code{N}, \code{R}, and \code{W} to their
%% needs, even if \code{R + W {\textless}= N}.  This means that the user
%% can achieve either strong or eventual consistency.  When a user picks
%% eventual consistency, and even when the programmer opts for strong
%% consistency but \code{W} is less than \code{N}, there are periods in
%% which replicas might not see eye-to-eye.  To provide eventual
%% consistency among replicas, these systems employ various tools to
%% catch stale replicas up to speed.  Let's first cover how various
%% systems determine that data has gotten out of sync, then discuss how
%% they synchronize replicas, and finally bring in a few dynamo-inspired
%% methods for speeding up the synchronization process.
DynamoベースのシステムであるVoldemortやCassandraそしてRiakなどでは、ユーザーが必要に応じて\code{N}や\code{R}、\code{W}を指定できるようにしている。\code{R + W {\textless}= N}であってもかまわない。つまり、強整合性と結果整合性のどちらを達成するのかをユーザーが選択できるということだ。ユーザーが結果整合性を選択した場合、仮にプログラマーが強整合性を望んだとしても、\code{W} {\textless} \code{N}ならレプリカを安心して扱えない。レプリカ間での結果整合性を提供するには、システム側でさまざまなツールを使ってレプリカを最新状態に保つことになる。まずは、さまざまなシステムがどのようにしてデータが古くなったことを検出するのかを見ていこう。それから、レプリカを同期する方法を考える。そして最後に、同期プロセスを高速化するためのDynamoの影響を受けた方法をいくつか紹介する。

%% \begin{aosasect3}{Versioning and Conflicts}
\begin{aosasect3}{バージョニングと衝突}

%% Because two replicas might see two different versions of a value for
%% some key, data versioning and conflict detection is important.  The
%% dynamo-based systems use a type of versioning called \emph{vector
%% clocks}.  A vector clock is a vector assigned to each key which
%% contains a counter for each replica.  For example, if
%% servers \code{A}, \code{B}, and \code{C} are the three replicas of
%% some key, the vector clock will have three entries, \code{(N\_A, N\_B,
%% N\_C)}, initialized to \code{(0,0,0)}.
あるキーについて、二つのレプリカが違うバージョンの値を返す可能性がある以上、データのバージョン管理や衝突の検出が重要になる。Dynamoベースのシステムで使っているバージョニング方式が\emph{ベクタークロック}だ。ベクタークロックとは、各キーにベクターを割り当て、そこにレプリカのカウンタを含める方式である。たとえば、何らかのキーのレプリカを\code{A}と\code{B}そして\code{C}で扱うとする。このときベクタークロックには三つのエントリ\code{(N\_A, N\_B, N\_C)}があり、その初期値は\code{(0,0,0)}となる。

%% Each time a replica modifies a key, it increments its counter in the
%% vector.  If B modifies a key that previously had version \code{(39, 1,
%% 5)}, it will change the vector clock to \code{(39, 2, 5)}.  When
%% another replica, say \code{C}, receives an update from B about the
%% key's data, it will compare the vector clock from \code{B} to its own.
%% As long as its own vector clock counters are all less than the ones
%% delivered from \code{B}, then it has a stale version and can overwrite
%% its own copy with \code{B}'s.  If \code{B} and \code{C} have clocks in
%% which some counters are greater than others in both clocks, say
%% \code{(39, 2, 5)} and \code{(39, 1, 6)}, then the servers recognize
%% that they received different, potentially unreconcilable updates over
%% time, and identify a conflict.
レプリカ上でキーの値が変更されるたびに、ベクター内でそれに対応するカウンタが加算される。直前のバージョンが\code{(39, 1, 5)}だったときにBがキーの値を変更すると、ベクタークロックは\code{(39, 2, 5)}に書き換わる。別のレプリカ、たとえば\code{C}がBからそのキーのデータの更新を受け取るときには、\code{B}からのベクタークロックを自分のものと比較する。自分のベクタークロックカウンタのほうが\code{B}から受け取ったものよりも小さい場合、自分のデータは古いバージョンなのであるから\code{B}の内容で上書きできる。\code{B}より\code{C}のほうが大きいカウンタとその逆のカウンタが両方ある場合、たとえば\code{(39, 2, 5)}と\code{(39, 1, 6)}などのようになった場合は、矛盾する更新があったとサーバーが判断して衝突したとみなす。

\end{aosasect3}

%% \begin{aosasect3}{Conflict Resolution}
\begin{aosasect3}{衝突の解決}

%% Conflict resolution varies across the different systems.  The Dynamo
%% paper leaves conflict resolution to the application using the
%% storage system.  Two versions of a shopping cart can be merged into
%% one without significant loss of data, but two versions of a
%% collaboratively edited document might require human reviewer to
%% resolve conflict.  Voldemort follows this model, returning multiple
%% copies of a key to the requesting client application upon conflict.
衝突の解決方法は、システムによってさまざまである。Dynamoの論文では、衝突の解決はストレージシステムを使うアプリケーション側に任せている。二つのバージョンのショッピングカートを一つにまとめるのはそれほど面倒ではないだろうが、共同作業で編集していた文書の複数バージョンをまとめる際の衝突は人間のレビューがないと解決できないだろう。Voldemortはこのモデルを採用しており、あるキーに対して複数のコピーを返し、クライアントアプリケーション側での対応を求める。

%% Cassandra, which stores a timestamp on each key, uses the most
%% recently timestamped version of a key when two versions are in
%% conflict.  This removes the need for a round-trip to the client and
%% simplifies the API. This design makes it difficult to handle
%% situations where conflicted data can be intelligently merged, as in
%% our shopping cart example, or when implementing distributed counters.
%% Riak allows both of the approaches offered by Voldemort and Cassandra.
%% CouchDB provides a hybrid: it identifies a conflict and allows users
%% to query for conflicted keys for manual repair, but deterministically
%% picks a version to return to users until conflicts are repaired.
Cassandraは各キーのタイムスタンプを格納しており、二つのバージョンが衝突する場合は一番タイムスタンプの新しいバージョンを採用する。これによってクライアントとのやりとりの必要をなくし、APIを単純化している。この設計では、衝突したデータを先ほどのショッピングカートの例のように自動マージすることは難しいし、分散カウンタを実装するのも困難だ。Riakは、VoldemortとCassandraのどちらの手法でも使える。CouchDBはハイブリッド方式だ。衝突を検出したら、ユーザー側でそのキーを手動で修復させるよう問い合わせ、衝突が解決するまでは特定のバージョンを確定的に採用してユーザーに返すようになっている。

\end{aosasect3}

%% \begin{aosasect3}{Read Repair}
\begin{aosasect3}{リードリペア}

%% If R replicas return non-conflicting data to a coordinator, the
%% coordinator can safely return the non-conflicting data to the
%% application.  The coordinator may still notice that some of the
%% replicas are out of sync.  The Dynamo paper suggests, and Cassandra,
%% Riak, and Voldemort implement, a technique called \emph{read repair}
%% for handling such situations.  When a coordinator identifies a
%% conflict on read, even if a consistent value has been returned to the
%% user, the coordinator starts conflict-resolution protocols between
%% conflicted replicas.  This proactively fixes conflicts with little
%% additional work.  Replicas have already sent their version of the data to
%% the coordinator, and faster conflict resolution will result in less
%% divergence in the system.
R台のレプリカが衝突していないデータをコーディネーターに返せたら、コーディネーターはその衝突していない値を安全にアプリケーションに返せる。それでもコーディネーターは、同期ができていないレプリカがあることを検出するかもしれない。そんな場合に使えるテクニックとしてDynamoの論文で提案されており、CassandraやRiakそしてVoldemortが実装しているのが\emph{リードリペア}だ。コーディネーターが読み込み時に衝突を検出すると、たとえ整合性のある結果をユーザーに返せたとしても、コーディネーターは衝突したレプリカの衝突解決プロトコルを開始する。これで、追加作業を最小限にしながら能動的に衝突を解消できる。各レプリカは既に自分の持つデータをコーディネーターに送っているので、早期に衝突を解決すればシステム内でのデータの相違を抑えられる。

\end{aosasect3}

%% \begin{aosasect3}{Hinted Handoff}
\begin{aosasect3}{Hinted Handoff}

%% Cassandra, Riak, and Voldemort all employ a technique called
%% \emph{hinted handoff} to improve write performance for situations
%% where a node temporarily becomes unavailable. If one of the replicas
%% for a key does not respond to a write request, another node is
%% selected to temporarily take over its write workload.  Writes for the
%% unavailable node are kept separately, and when the backup node notices
%% the previously unavailable node become available, it forwards all of
%% the writes to the newly available replica.  The Dynamo paper utilizes
%% a 'sloppy quorum' approach and allows the writes accomplished through
%% hinted handoff to count toward the W required write acknowledgments.
%% Cassandra and Voldemort will not count a hinted handoff against W, and
%% will fail a write which does not have W confirmations from the
%% originally assigned replicas.  Hinted handoff is still useful in these
%% systems, as it speeds up recovery when an unavailable node returns.
CassandraやRiakそしてVoldemortはすべて、\emph{Hinted Handoff}というテクニックを使っている。これは、どれか一つのノードが一時的に使えなくなっている状態での書き込みのパフォーマンスを向上させるテクニックだ。あるキーに対応するレプリカの一つが書き込みリクエストに反応しなかったときに、別のノードを選択して一時的にその書き込み処理を引き継がせる。反応しなかったノードへの書き込みは個別に続けられ、反応しなかったノードが復旧したことをバックアップノードが知った時点で、そのレプリカに新しい書き込みをすべて転送する。Dynamoの論文では'sloppy quorum'という手法を利用しており、Hinted Handoffで書き込まれたノードも書き込みの成功判断基準であるWにカウントできるようにしている。CassandraやVoldemortはHinted HandoffのぶんをWにカウントせず、本来割り当てられているレプリカの中でWに満たない場合は書き込みに失敗する。それでもなおHinted Handoffは有用だ。というのも、反応しなくなったノードが復旧したときのリカバリーを高速に行えるからである。

\end{aosasect3}

%% \begin{aosasect3}{Anti-Entropy}
\begin{aosasect3}{Anti-Entropy}

%% When a replica is down for an extended period of time, or the machine
%% storing hinted handoffs for an unavailable replica goes down as well,
%% replicas must synchronize from one-another.  In this case, Cassandra
%% and Riak implement a Dynamo-inspired process called
%% \emph{anti-entropy}.  In anti-entropy, replicas exchange \emph{Merkle
%% Trees} to identify parts of their replicated key ranges which are
%% out of sync.  A Merkle tree is a hierarchical hash verification: if
%% the hash over the entire keyspace is not the same between two
%% replicas, they will exchange hashes of smaller and smaller portions of
%% the replicated keyspace until the out-of-sync keys are identified.
%% This approach reduces unnecessary data transfer between replicas which
%% contain mostly similar data.
あるレプリカのダウン長期間になったり、ダウンしたレプリカをHinted Handoffで引き継いだマシン自体もまたダウンしてしまった場合、レプリカはお互いに同期しなければならない。この場合にCassandraやRiakが使う手順は、Dynamoに影響を受けた\emph{Anti-Entropy}というものだ。Anti-Entropyにおいて、各レプリカは\emph{マークル木(Merkle Trees)}を交換する。これは、担当するキー範囲のうち最新状態と同期できていない部分を識別するものだ。マークル木とは、ハッシュの検証を階層的に行うものだ。もしキー空間全体のハッシュが二つのレプリカで一致しなければ、レプリケートしているキー空間のより小さい部分のハッシュを順に交換していき、同期できていないキーが特定できるまでそれを続ける。この手法により、ほとんど同じ状態で一部だけ違うというレプリカの間でのデータ交換の量を減らせる。

\end{aosasect3}

%% \begin{aosasect3}{Gossip}
\begin{aosasect3}{Gossip}

%% Finally, as distributed systems grow, it is hard to keep track of how
%% each node in the system is doing.  The three Dynamo-based systems
%% employ an age-old high school technique known as \emph{gossip} to keep
%% track of other nodes.  Periodically (every second or so), a node will
%% pick a random node it once communicated with to exchange knowledge of
%% the health of the other nodes in the system.  In providing this
%% exchange, nodes learn which other nodes are down, and know where to
%% route clients in search of a key.
分散システムが成長するにつれ、システム内の個々のノードが何をしているのかを追跡するのが難しくなってくる。Dynamoベースの三つのシステムが他のノードを追跡するために使っているのは、\emph{Gossip}という昔ながらのテクニックだ。定期的(毎秒など)に、あるノードがランダムに別のノードを選んでお互いに通信し、自分が知っている他のノードの健康状態を交換する。このようにすることで各ノードは他のノードがダウンしているかどうかを知ることができ、クライアントからのキーの検索要求をどこに振ればいいかもわかるようになる。

\end{aosasect3}

\end{aosasect2}

\end{aosasect1}

%% \begin{aosasect1}{A Final Word}
\begin{aosasect1}{最後に}

%% The NoSQL ecosystem is still in its infancy, and many of the
%% systems we've discussed will change architectures, designs, and
%% interfaces.  The important takeaways in this chapter are not what
%% each NoSQL system currently does, but rather the design decisions that
%% led to a combination of features that make up these systems.  NoSQL
%% leaves a lot of design work in the hands of the application designer.
%% Understanding the architectural components of these systems will not
%% only help you build the next great NoSQL amalgamation, but also allow
%% you to use current versions responsibly.
NoSQLを取り巻く世界はまだ成熟しておらず、今回議論したシステムの多くもそのアーキテクチャや設計そしてインターフェイスを変えていくかもしれない。本章を読んで得られるものは、個々のNoSQLシステムが現時点で何をしているかということではない。これらのシステムが、どのような決断を経て現在の機能セットに至ったのかということだ。NoSQLは、設計作業の多くをアプリケーション側の設計に委ねた。これらのシステムのアーキテクチャについて理解すれば、単に次世代のすばらしいNoSQLシステムを作るにとどまらず、現時点のバージョンを責任を持って使えるようにする手助けになることだろう。

\end{aosasect1}

%% \begin{aosasect1}{Acknowledgments}
\begin{aosasect1}{謝辞}

%% I am grateful to Jackie Carter, Mihir Kedia, and the anonymous
%% reviewers for their comments and suggestions to improve the chapter.
%% This chapter would also not be possible without the years of dedicated
%% work of the NoSQL community.  Keep building!
Jackie CarterやMihir Kedia、そして匿名のレビューアのみなさんに感謝する。みなさんのコメントや提案が本章の改善に大いに役立った。また本章は、NoSQLコミュニティの長年の作業がなければ存在し得なかった。これからもぜひこの調子で!

\end{aosasect1}

\end{aosachapter}
